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

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

알고리즘 교수님은 학생들에게 병합 정렬을 이용해 오름차순으로 정렬하는 과제를 내려고 한다.

정렬 된 결과만으로는 실제로 병합 정렬을 적용했는지 알 수 없기 때문에 다음과 같은 제약을 주었다.

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,000

출력

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

예제

입력

3
5
2 2 1 1 3
10
7 5 4 1 2 10 3 6 9 8
100
158 56 163 106 108 153 159 147 93 140 126 9 145 166 191 106 48 183 184 115 197 136 45 196 175 89 199 52 186 170 199 28 190 40 83 48 151 35 128 4 13 38 65 20 76 142 23 63 30 30 178 36 32 114 79 68 2 187 106 98 67 131 109 177 20 113 1 102 172 119 197 190 28 82 165 168 60 18 156 174 78 42 110 63 56 66 191 105 72 108 104 198 179 132 99 189 183 91 28 162 

출력

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

My Sol

def merge_sort(arr, l):
    if l < 2:
        return arr, l

    mid = l//2
    arr_low, ll = merge_sort(arr[:mid], mid)
    arr_high, lh = merge_sort(arr[mid:], l-mid)

    if arr_low[-1] > arr_high[-1]:
        global cnt
        cnt += 1

    merged_arr = []
    low = high = 0
    while low < mid and high < l-mid:
        if arr_low[low] < arr_high[high]:
            merged_arr.append(arr_low[low])
            low += 1
        else:
            merged_arr.append(arr_high[high])
            high += 1

    merged_arr += arr_low[low:]
    merged_arr += arr_high[high:]

    return merged_arr, ll+lh


T = int(input())
for tc in range(1, T+1):
    N = int(input())
    arr = list(map(int, input().split()))
    cnt = 0
    arr2, l2 = merge_sort(arr, N)

    print(f'#{tc} {arr2[N // 2]} {cnt}')

합병 정렬을 인덱스로 구현하는 템플릿을 이용해 합병 정렬 함수를 작성하였다. 그리고 각 분할 구역의 마지막 원소 값을 비교하는 로직을 추가하여 전역변수 cnt를 올려주고 정렬이 끝나면 이를 출력하도록 하였다.

결과

PASS