[백준] 24060. 알고리즘 수업 - 병합정렬1

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

분류

• 구현
• 정렬
• 재귀

문제 설명

오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.

크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다.

의사코드는 링크 참조

입력

첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다.

다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

출력

배열 A에 K 번째 저장 되는 수를 출력한다. 저장 횟수가 K 보다 작으면 -1을 출력한다.

문제풀이

병합 정렬 로직을 그대로 참고하되 빈 배열(ans)을 만들고 정렬되는 순서대로 추가만 해주면 된다. 마지막에 k길이보다 작으면 -1을, 같거나 크다면 배열의k-1 값을 출력해주면 된다.

병합정렬: 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬 에 속하며, 분할 정복 알고리즘의 하나다.

병합정렬의 풀이 순서

• 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
• 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
• 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
• 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

python 문제 풀이

import sys
input = sys.stdin.readline


def mergeSort(L):
    if len(L) == 1:
        return L
    
    mid = (len(L) + 1)//2
    left = mergeSort(L[:mid])
    right = mergeSort(L[mid:])
    
    L2 = []
    i = 0
    j = 0
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            L2.append(left[i])
            ans.append(left[i])
            i += 1
        else:
            L2.append(right[j])
            ans.append(right[j])
            j += 1
    
    while i < len(left):
        L2.append(left[i])
        ans.append(left[i])
        i += 1
        
    while j < len(right):
        L2.append(right[j])
        ans.append(right[j])
        j += 1
        
    return L2

n, k = map(int, input().split())
a = list(map(int, input().split()))

ans = []
mergeSort(a)

if len(ans) >= k:
    print(ans[k-1])
else:
    print(-1) 

참고

• [🥈4 / 백준 24060 / 파이썬] 알고리즘 수업 - 병합 정렬 1
  
• [알고리즘] 합병 정렬(merge sort)이란