[백준] 24060번 알고리즘 수업 - 병합 정렬 1 (파이썬)

문제

24060번: 알고리즘 수업 - 병합 정렬 1

이 문제는 자리수를 /2를 계속하여 최대한 줄인 다음에 오름차순으로 정렬하는 문제이다.

예를 들어 4 5 1 3 2라면 

[4, 5, 2], [3, 2]  → [4, 5], [1], [3, 2] → [4] [5], [1], [3], [2] → [4, 5], [1], [3], [2] → [1, 4, 5], [2, 3] → [1, 2, 3, 4, 5]

이런식으로 변한다.

코드

import sys
input = sys.stdin.readline

def m_sort(a):
    if len(a) == 1:
        return a

    mid = (len(a) + 1) // 2

    # a_1이 하나 남을때까지 쪼개줘
    a_1 = m_sort(a[ : mid])
    # a_1을 제외하고 하나 남을때까지 쪼개줘
    a_2 = m_sort(a[mid : ])

    i, j = 0, 0
    li_2 = []
    while i < len(a_1) and j < len(a_2):
        if a_1[i] < a_2[j]:
            a_li.append(a_1[i])
            li_2.append(a_1[i])
            i += 1
        else:
            a_li.append(a_2[j])
            li_2.append(a_2[j])
            j += 1

    while i < len(a_1):
        a_li.append(a_1[i])
        li_2.append(a_1[i])
        i += 1

    while j < len(a_2):
        a_li.append(a_2[j])
        li_2.append(a_2[j])
        j += 1

    # a_1으로 리턴
    return li_2

N, K = map(int, input().split())
A = list(map(int, input().split()))

a_li = []
m_sort(A)

print(a_li)
if len(a_li) > K:
    print(a_li[K - 1])
else:
    print(-1)​

해설

재귀함수를 이용하여 나눌수 있는 만큼 최대한 나누고 변화대는 숫자를 순서대로 li_2에 넣어준다. 

후에 k-1번의 순서의 숫자를 찾아준다 없다면 -1를 반환한다.