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

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

문제 요약

접근 방식

병합 정렬(Merge Sort)의 동작 과정 중, 정렬된 값을 리스트에 저장하는 시점을 추적하여 K번째 저장되는 값을 찾는 방식으로 구현

해결 코드

import sys
input = sys.stdin.readline  # 빠른 입력 사용 (백준에서 필수)

# 병합 정렬 함수 정의
def mergeSort(L):
    # 리스트 길이가 1이면 더 이상 분할할 수 없으므로 그대로 반환
    if len(L) == 1:
        return L
    
    # 리스트를 반으로 나누기 (홀수일 때 왼쪽이 더 많게)
    mid = (len(L) + 1) // 2
    left = mergeSort(L[:mid])   # 왼쪽 반 정렬
    right = mergeSort(L[mid:])  # 오른쪽 반 정렬
    
    # 병합을 위한 리스트 초기화
    L2 = []
    i = j = 0
    
    # 왼쪽, 오른쪽 리스트를 비교하며 정렬된 값을 하나씩 넣기
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            L2.append(left[i])      # 정렬된 결과 저장
            ans.append(left[i])     # 저장된 값을 ans에 기록 (몇 번째 저장인지 세기 위함)
            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())            # n: 배열 길이, k: 저장 횟수
a = list(map(int, input().split()))         # a: 입력 배열

ans = []                    # 병합 중 저장된 값을 기록할 리스트
mergeSort(a)                # 병합 정렬 수행

# 저장 횟수가 K 이상이면 K번째 저장된 값 출력, 아니면 -1 출력
if len(ans) >= k:
    print(ans[k-1])         # K번째 저장된 값 (0-indexed라서 k-1)
else:
    print(-1)