[백준/파이썬/24060] 알고리즘 수업 - 병합 정렬 1 _ 풀이

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

 

---

 

 

---

 

풀이

def merge_sort(arr, f, l):
    if f < l:
        mid = (f + l) // 2
        merge_sort(arr, f, mid)
        merge_sort(arr, mid + 1, l)
        merge(arr, f, mid, l)
    
# arr[f~mid]까지와 arr[mid+1~l]까지를 오름차순으로 병합
def merge(arr, f, m, l):
    global cnt, answer
    i = f; j = m+1
    temp = []
    
    while i <= m and j <= l:
        if arr[i] <= arr[j]:
            temp.append(arr[i])
            i += 1 
        else:
            temp.append(arr[j])
            j += 1 
    
    # 왼쪽 배열 부분이 남은 경우
    while i <= m:
        temp.append(arr[i])
        i += 1
    # 오른쪽 배열 부분이 남은 경우
    while j <= l:
        temp.append(arr[j])
        j += 1 
    
    i = f 
    t = 0
    # 정렬된 배열을원본 배열에 반영
    while i <= l:
        arr[i] = temp[t]
        cnt += 1
        if cnt == save_count:
            answer = arr[i]
            break
        i += 1
        t += 1
        

length, save_count = map(int, input().split())
arr = list(map(int, input().split()))
cnt = 0
answer = -1
merge_sort(arr, 0, length - 1)
print(answer)

 

 

문제의 의사코드를 그대로 구현하면 된다.

병합 정렬 연습하기 좋은 문제다.