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

사용 언어 - Python3

백준 24060번: 알고리즘 수업 - 병합 정렬 1 (실버4, 정렬)

문제 ★병합 정렬 문제★

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

 

 

정답

병합 정렬(분할 정복 알고리즘) 문제

(코드 풀이) 병합 정렬 의사 코드에서 추가되는 포인트 정리

0. merge_sort(), merge() 굳이 분리할 필요 없음

1. len(L)이 1이라면 정렬할 게 없으므로 return L

2. mid = ((len(L)+1)//2

45 132가 아닌 451 32로 앞이 크도록 병합하기 때문에 mid변수 기준을 +1해준다.

 

3. left, right 리스트 활용

q = len(left), r = len(right)

 

4. 빈 리스트 ans에 정렬되는 순서대로 추가해주는 방식

병합정렬이 끝난 뒤, len(ans)가

k길이보다 작으면 -1을 return / k길이보다 같거나 크면 ans[k-1]을 return

 

import sys
input = sys.stdin.readline

def merge_sort(L):
    if len(L) == 1:
        return L
    
    mid = (len(L)+1)//2
   
    left = merge_sort(L[:mid])
    right = merge_sort(L[mid:])
    
    i,j = 0,0
    L2 = []
    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 = []
merge_sort(a)

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

 

---

레퍼런스

• 정답 참고

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

• 깃허브 정답

GitHub - yyeongeun/codingtest: 코딩테스트 공부