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

내가 작성한 코드

def merge_sort(a, s, e):
    if s < e:
        p = (e + s) // 2
        merge_sort(a, s, p)
        merge_sort(a, p + 1, e)
        merge(a, s, p, e)
        


def merge(a, s, p, e):
    global cnt
    global ret
    if cnt <= 0:
        return
    i = s
    j = p + 1
    temp = []    
    while i <= p and j <= e:
        if a[i] <= a[j]:            
            temp.append(a[i])
            i += 1
        else:            
            temp.append(a[j])
            j += 1
        cnt -= 1
        if cnt == 0:
            ret = temp[-1]
    while i <= p:
        temp.append(a[i])
        i += 1
        cnt -= 1
        if cnt == 0:
            ret = temp[-1]
    while j <= e:
        temp.append(a[j])
        j += 1
        cnt -= 1
        if cnt == 0:
            ret = temp[-1]
    for i in range(len(temp)):
        a[s + i] = temp[i]


N, K = map(int, input().split())
a = list(map(int, input().split()))
global cnt
global ret
cnt = K
ret = -1
merge_sort(a, 0, N - 1)
print(ret)

고민한 사항

1. a배열에 정렬된 것으로 초기화 할 때 s의 인덱스를 더해주어 저장하는 위치를 잡아주어야 한다.
2. 홀수의 개수를 병합 정렬시 2 : 1로 쪼개어 하나의 값만을 갖는 부분은 정렬할 것이 없으므로 앞서 정렬된 배열과 비교하여 바로 정렬하면 된다.
3. k번째 저장되는 수를 구하기위해 k값을 함수 내부에서 매개변수로 식별하지 않고 전역 변수로 모니터링 할 수 있도록 하였다.
4. k의 수가 재귀하여 저장하는 횟수보다 클때 -1을 출력해야하므로 전역으로 -1을 갖는 ret변수를 선언한뒤 k번째 저장되는 수로 ret을 초기화 해줌으로 써 해결하였다.
5. cnt가 0이라면 원하는 값을 얻어 더이상 정렬할 필요가 없으므로 return 해주었다.

cnt -= 1해주며 모든 삽입 부분을 모니터링하는 코드가 너무 지저분해 보여서 아쉽다.. 모니터링을 해주기 위해 어쩔 수 없이 넘어갔다..

다른 풀이
이 풀이와 나와의 차이점
1. merge_sort(a)의 리턴값을 left, right로 나누어 한번에 해결했다.
2. list[:mid] 처럼 슬라이스 방식을 사용하여 가독성을 높혔다.
3. ans 라는 list를 선언한 뒤 값을 추가할 때마다 같이 추가하여 마지막에 ans[k - 1]로 몇번째에 넣었는지 식별할 수 있도록 했다는 점이다.

결과