[SWEA #11891] 분할정복 - 병합정렬

문제

알고리즘 교수님은 학생들에게 병합 정렬을 이용해 오름차순으로 정렬하는 과제를 내려고 한다.
정렬 된 결과만으로는 실제로 병합 정렬을 적용했는지 알 수 없기 때문에 다음과 같은 제약을 주었다.
N개의 정렬 대상을 가진 리스트 L을 분할할 때 L[0:N//2], L[N//2:N]으로 분할 한다.
병합 과정에서 다음처럼 왼쪽 마지막 원소가 오른쪽 마지막 원소보다 큰 경우의 수를 출력한다.

정렬이 끝난 리스트 L에서 L[N//2] 원소를 출력한다.
알고리즘 교수님의 조건에 따라 병합 정렬을 수행하는 프로그램을 만드시오.

 

입력

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50
다음 줄부터 테스트 케이스의 별로 정수의 개수 N이 주어지고, 다음 줄에 N개의 정수 ai가 주어진다.
5<=N<=1,000,000, 0 <= ai <= 1,000,00

 

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤,  N//2 번째 원소와 오른쪽 원소가 먼저 복사되는 경우의 수를 출력한다.

 

내가 쓴 코드 1 (틀림)

def merge_sort(lst):
    global cnt
    n = len(lst)
    if n <= 1:
        return lst

    mid = n // 2
    l = merge_sort(lst[:mid])
    r = merge_sort(lst[mid:])

    # 병합하기
    i = j = 0
    last_l = last_r = 0
    ret = []
    while i < len(l) and j < len(r):
        if l[i] <= r[j]:
            ret.append(l[i])
            i += 1
        else:
            ret.append(r[j])
            j += 1
        if i == len(l) - 1:
            last_l = l[i]
        if j == len(r) - 1:
            last_r = r[j]
    ret.extend(l[i:])
    ret.extend(r[j:])
    if last_l > last_r:
        cnt += 1
    return ret

T = int(input())
for t in range(T):
    N = int(input())
    arr = list(map(int, input().split()))
    cnt = 0
    sorted_arr = merge_sort(arr)
    print(f'#{t+1} {sorted_arr[N//2]} {cnt}')

 

내가 쓴 코드 2 (맞)

def merge_sort(lst):
    global cnt
    n = len(lst)
    if n <= 1:
        return lst

    mid = n // 2
    l = merge_sort(lst[:mid])
    r = merge_sort(lst[mid:])
    if l[-1] > r[-1]:
        cnt += 1
        
    # 병합하기
    i = j = 0
    ret = []
    while i < len(l) and j < len(r):
        if l[i] <= r[j]:
            ret.append(l[i])
            i += 1
        else:
            ret.append(r[j])
            j += 1

    ret.extend(l[i:])
    ret.extend(r[j:])
    return ret

T = int(input())
for t in range(T):
    N = int(input())
    arr = list(map(int, input().split()))
    cnt = 0
    sorted_arr = merge_sort(arr)
    print(f'#{t+1} {sorted_arr[N//2]} {cnt}')

분할된 리스트 중 왼쪽 마지막 원소가 오른쪽 마지막 원소보다 큰 경우의 수를 구하는 식이 틀렸다... 

넘무 어려워효...ㅠㅜ

 

출력 결과

#1 2 0
#2 6 6
#3 108 43