2장. 정렬

익숙함에 속아 소중함을 잃지 말자

오늘도 열심히 컴퓨터 앞에 앉아 알고리즘 공부를 하고 있는 엘리스를 바라본 체셔는 흐뭇해하며 문득 얼마나 공부를 했는지 궁금해졌습니다.

“엘리스! 정렬 알고리즘에 대해 알고 있니? 선택 정렬, 합병 정렬, 퀵..” 엘리스가 빠르게 답했습니다.

“정렬 알고리즘을 왜 공부해? Python에서는 sort() 내장함수만 쓰면 해결 된다구!”

순간 어이가 없어진 체셔는 엘리스에게 말했습니다.

“좋아 엘리스! 내가 sort() 함수를 못 쓰게 해줄 게 어디 한번 이것도 정렬해 보시지!”

정렬 알고리즘에 대해 아무것도 모르는 엘리스를 도와 n log(n) 속도의 정렬 알고리즘을 구현하세요!

이 실습에서는 sort()와 sorted()를 사용할 수 없습니다.

• 입력 예시

3 5 1 2 9 6 4 5 7

• 출력 예시

1 2 3 4 5 5 6 7 9

• 입력
  • 자연수NN이 각각 공백을 기준으로 주어집니다.
  • 주어지는 NN의 개수는 3이상 10만 이하입니다.
• 출력
  • 주어진 자연수 NN을 오름차순으로 정렬하세요.

def quick(arr):
    
    if len(arr) <= 1:
        return arr

    pivot = arr[0]
    
    left = []
    right = []
    
    for i in range(1,len(arr)):
        if arr[i] <= pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    
    return quick(left) + [pivot] + quick(right)

arr = list(map(int, input().split()))

arr = map(str,quick(arr))

print(' '.join(arr))

내 맘대로 문자열 배치

체셔로 인해 정렬 알고리즘에 대해 관심이 생긴 엘리스는 자신만의 정렬 알고리즘을 만들어 보려고 합니다.

엘리스가 떠올린 아이디어는 자신이 좋아하는 알파벳 소문자로 이루어진 문자열을 정하고 그 문자열을 기준으로 문자열을 정렬하는 방법입니다.

하지만 오늘도 정렬 알고리즘에 대해 잘 모르는 엘리스는 아이디어만 있고 만들고는 있지 못하는 실정입니다. 여러분이 엘리스를 위해 대신 프로그램을 만들어주세요.

• 입력 예시

zyx
nicyetomexetzu

• 출력 예시

zyxnicetomeetu

• 입력
  • 첫 번째 줄에 정렬의 기준이 되는 문자열이 주어집니다. 이 문자열은 알파벳 소문자로만 이루어져있습니다.
  • 두 번째 줄에 정렬해야할 문자열이 주어집니다. 이 문자열의 길이는 5이상 200 이하 입니다.
• 출력
  • 첫 번째로 입력받은 문자열을 기준으로 두 번째로 입력 받은 문자열을 정렬하세요.

def sort_my(Str, standard, cnt):

    if cnt == len(standard):
        return Str
    
    sort_str = ''
    tmp = ''
    
    for c in Str:
        if c == standard[cnt]:
            sort_str+=c
        else:
            tmp+=c

    return sort_str + sort_my(tmp,standard,cnt+1)

standard = input()
Str = input()

print(sort_my(Str, standard, 0))

당신의 분할은?

체셔를 통해 정렬 알고리즘의 중요성을 깨달은 엘리스는 체셔에게 자신있게 말했습니다.

“체셔! 나 이제 정렬 알고리즘에 대해서 마스터 한것 같아. 정말 뿌듯해!”

체셔가 답했습니다.

“그래?? 정말 뿌듯하네! 그럼 이제 분할 정복 알고리즘 문제를 해결하는데 문제없겠네??”

엘리스는 무엇인지 모를 오한을 느꼈지만 개의치 않았습니다.

“응!!! 당연하지! 내가 누군데!”

체셔는 저번과 같은 환한 미소를 지으며 말했습니다.

“좋아! 그럼 엘리스가 숫자로 이루어진 배열을 분할 정복 알고리즘으로 정렬을 하려고 할 때 최대 몇 가지 배열로 분할할 수 있을까??”

오늘도 무사히 넘어갈 리 없는 체셔에게 엘리스는 또 속았습니다!! 여러분이 엘리스를 도와 대신 대답해주세요.

일련의 숫자로 이루어진 배열이 주어집니다.

이 배열을 몇 개의 배열로 나누어야 정렬을 할 수 있을까요?

• 입력 예시 1

3 2 1 0

• 출력 예시 1

1 

[3, 2, 1, 0]을 [3, 2] 와 [1, 0]으로 분할한다면 [2 ,3], [0,1] 이 되므로 분할 할 수 없습니다.

• 입력 예시 2

2 3 0 1 4 5

• 출력 예시 2

3

[2, 3, 0, 1]과 [4], [5]로 분할한다면 [0,1,2,3]과 [4],[5]로 정렬 할 수 있습니다.

• 입력
  • 0 이상의 정수들로 이루어진 배열 A가 입력됩니다.
  • 배열 A의 길이를 N이라고 하겠습니다.
  • 배열 A에 들어 있는 정수들은, 0 이상 N 미만의 자연수이며 서로 중복되지 않습니다.
• 출력
  • 주어진 배열(ArrayArray)를 여러 부분 배열로 나누고, 각 부분 배열을 정렬한 후 이어붙일 때 전체 배열이 정렬된 상태가 되는 경우 중, 나눌 수 있는 부분 배열의 최대 개수를 출력하세요.

arr = list(map(int, input().split()))

cnt = 0

sum_index = 0
sum_value = 0

for i in range(len(arr)):
    sum_index+=i
    sum_value+=arr[i]
    if sum_index == sum_value:
        cnt+=1
        
print(cnt)

최강의 패

남녀노소 모두가 즐길 수 있는 코더랜드 고유의 전통 놀이가 있습니다. 이 놀이의 이름은 바로 수투!

수투를 즐기는 법은 간단합니다. 자연수로만 이루어진 카드 뭉치에서 일정한 수의 카드를 뽑아 최고로 큰 숫자를 만드는 사람이 이기는 방식입니다.

엘리스와 토끼, 체셔, 모자장수는 둘러앉아 게임 수투를 시작했습니다. 시간이 지나고 엘리스는 계속 지기만 하는 자기 자신을 마주할 수 밖에 없었습니다!

“엘리스 이 바보야. 넌 2, 10, 5 를 받았잖아 그럼 1052이 제일 큰 수가 아니라 5210이 제일 큰 수야.” 체셔가 말했습니다.

“아! 그렇구나.” 엘리스가 답했습니다.

이대로 가다간 엘리스는 한 판도 못 이기겠습니다. 여러분이 엘리스를 도와 최고로 높은 수를 찾아주세요!

• 입력 예시

5 2 52 100

• 출력 예시

5522100

• 입력
  • 자연수로 이루어진 숫자(NumberNumber) 리스트가 주어집니다.
  • 주어지는 NumberNumber의 길이는 1 ≤ NumberNumber ≤ 1,000 입니다.
• 출력
  • 주어진 숫자(NumberNumber) 리스트로 조합 할 수 있는 숫자 중 가장 큰 숫자를 출력하세요.
  • 숫자가 너무 커질 수 있으니 문자열 형태로 출력합니다.

arr = input().split()

for i in range(len(arr)-1):
    for j in range(len(arr)-1-i):
        if arr[j]+arr[j+1] <= arr[j+1]+arr[j]:
            arr[j],arr[j+1] = arr[j+1],arr[j]
            
print(''.join(arr))

흰토끼의 장사하자

오늘도 열심히 알고리즘 공부 중인 엘리스에게 왕궁에서 은퇴한 흰토끼가 찾아왔습니다.

“엘리스! 내가 붕어빵가게를 하나 차리려고 하는데 어느 위치에 음식점을 차려야 장사가 잘 될지 모르겠어.”

엘리스는 이런 흰토끼의 고민을 해결해줄 좋은 방법이 떠올랐습니다.

“흰토끼야, 우리 골목의 각 사람들까지의 거리의 합이 최소가 되는 위치에 붕어빵 가게를 차리자. 그러면 모두가 너무 멀지 않은 거리라서 자주 찾아 올거야!”

흰토끼는 붕어빵을 잔뜩 팔아 부자가 될 생각에 벌써부터 함박웃음을 짓고 있습니다. 여러분도 흰토끼의 행복한 노후를 위해 엘리스를 도와 프로그램을 완성해주세요!

흰토끼가 붕어빵 장사를 하려는 골목은 일직선입니다. 우리에게 주어진 정보는 골목에 있는 집들의 위치와 그 집에 사는 사람들의 정보입니다.

• 입력 예시

5
1 3
2 7
3 10
4 5
5 5

• 출력 예시

3

• 입력
  • 첫 번째 줄에 골목에 있는 집들의 수가 주어집니다. 이 집의 수는 1이상 100,000이하입니다.
  • 두 번째 줄부터 집의 위치와 그 집에 사는 사람의 수가 공백을 기준으로 나뉘어 주어집니다. 이 수는 모두 100,000,000 이하의 자연수입니다,
• 출력
  • 흰토끼의 붕어빵가게의 위치를 출력합니다.

N = int(input())

location_num = []

Max = 0

for i in range(N):
    location_num.append(list(map(int, input().split())))
    Max = max(Max, location_num[i][0])

location_num.sort()

Sum = 0
left = 0
right = 0

arr = [0 for i in range(Max+1)]

for i in range(N):
    arr[location_num[i][0]] = location_num[i][1]
    
#print(arr)

for i in range(location_num[0][0]+1,Max+1):
    Sum+=arr[i]*(i-1)
    right+=arr[i]

Min = 999999999999999999
Min_index = 0

#print(Sum)
#print()

if Min > Sum:
    Min = Sum
    Min_index = location_num[0][0]

for i in range(location_num[0][0]+1,Max+1):
    left+=arr[i-1]
    Sum-=right
    Sum+=left
    right-=arr[i]
    #print(Sum, left, right)
    if Min > Sum:
        Min = Sum
        Min_index = i
print(Min_index)