백준 24060 : 알고리즘 수업 - 병행정렬 [파이썬]

https://www.acmicpc.net/problem/24060

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

1 . 코드 설명 

병합 정렬을 재귀 알고리즘으로 풀어가는 방식이였다. 병합 정렬부터 공부하고 시작했다.

이렇게 앞뒤를 나눠서 정렬해 나가면서 조합하는 방식이였다.

k는 번째로 정렬한 수이다. 배열 A는 [ 3, 4, 1, 3, 4, 2, 5, 1, 2, 3, 4, 5] 이런 식으로 나온다.

 

2. 예

앞서 설명한대로 앞뒤로 쪼개 앞에서 부터 하나씩 정렬해 나가는 방식이다.

 

3. 코드

# import sys
# input = sys.stdin.readline

def merge_sort(ll):
    if len(ll) == 1:
        return ll
    
    mid = (len(ll)+1)//2

    left = merge_sort(ll[:mid])
    right = merge_sort(ll[mid:])

    i, j = 0, 0

    lll = []
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            lll.append(left[i])
            ans.append(left[i])
            i+=1
        else:
            lll.append(right[j])
            ans.append(right[j])
            j+=1
    while i < len(left):
        lll.append(left[i])
        ans.append(left[i])
        i+=1
    while j < len(right):
        lll.append(right[j])
        ans.append(right[j])
        j+=1
    
    return lll

n, m = map(int, input().split())
a = list(map(int,input().split()))
ans = []
merge_sort(a)

if m <= len(ans):
    print(ans[m-1])
else:
    print(-1)

맨위에 sys.stdin.readline은 jupyter notebook 환경이라 주석 처리 해두었다.(제출한다면 주석제거)

재귀로 5개부터 3개, 2개로 쪼개므로 가운데에서 1을 더해서 몫을 구했다.

하나하나 정렬하고 그값을 lll과 ans에 넣는다 lll은 재귀때마다 초기화를 해서 입력 순서는 안나오고 마지막 정렬된 값이 나온다. 

마지막으로 ans보다 큰 k값을 입력했을때와 아닐때를 구분해서 print 해주었다.