백준 재귀 단계: 24060번 병합정렬: 아직 해결 ❌

🛎️ 24060번 병합정렬 (재귀 알고리즘까지)

답은 맞았으나 문제가 원하는 과정이 아님

# 24060 병합 정렬 문제
#병합 정렬:
def merge_sort(a_list):
    r = 0
    t_list = []
    if (len(a_list) > 1):
        mid = len(a_list) // 2
        left_list = a_list[:mid]
        right_list = a_list[mid:]
        a,b = merge_sort(left_list)
        r += a
        t_list.extend(b)

        c,d = merge_sort(right_list)
        r += c
        t_list.extend(d)

        a_list_i = 0
        left_i = 0
        right_i = 0

        while left_i < len(left_list) and right_i < len(right_list):
            if(left_list[left_i] <= right_list[right_i]) :
                a_list[a_list_i] = left_list[left_i]
                t_list.append(left_list[left_i])
                left_i += 1
            else:
                a_list[a_list_i] = right_list[right_i]
                t_list.append(right_list[right_i])
                right_i += 1
            a_list_i += 1
            r += 1

        while left_i < len(left_list):
            a_list[a_list_i] = left_list[left_i]
            t_list.append(left_list[left_i])
            left_i += 1
            a_list_i += 1
            r += 1


        while right_i < len(right_list):
            a_list[a_list_i] = right_list[right_i]
            t_list.append(right_list[right_i])
            right_i += 1
            a_list_i += 1
            r += 1

    return r,t_list

x1,x2 = input().split( )
x1 = int(x1)
x2 = int(x2)

a_list = list(map(int,input().split()))

r,t_list = merge_sort(a_list)

if( x2 > len(t_list)):
    print(-1)
else:
    print(t_list[x2-1])

문제에서 시키는? 과정의 의사코드

merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
    if (p < r) then {
        q <- ⌊(p + r) / 2⌋;       # q는 p, r의 중간 지점
        merge_sort(A, p, q);      # 전반부 정렬
        merge_sort(A, q + 1, r);  # 후반부 정렬
        merge(A, p, q, r);        # 병합
    }
}

# A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
# A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
merge(A[], p, q, r) {
    i <- p; j <- q + 1; t <- 1;
    while (i ≤ q and j ≤ r) {
        if (A[i] ≤ A[j])
        then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
        else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
    }
    while (i ≤ q)  # 왼쪽 배열 부분이 남은 경우
        tmp[t++] <- A[i++];
    while (j ≤ r)  # 오른쪽 배열 부분이 남은 경우
        tmp[t++] <- A[j++];
    i <- p; t <- 1;
    while (i ≤ r)  # 결과를 A[p..r]에 저장
        A[i++] <- tmp[t++]; 
}