5204. [파이썬 S/W 문제해결 구현] 4일차 - 병합 정렬

이번 문제는 병합 정렬 문제인데, 정렬된 배열의 중간 값과 왼쪽 마지막 원소가 오른쪽 마지막 원소보다 큰 경우의 수도 출력해야 하는 문제이다.

# 오류가 난 코드

T = int(input())
for test_case in range(1, T+1):
    N = int(input())
    arr = list(map(int, input().split()))

    count = 0

    def merge_sort(m):
        global count
        
        if len(m) <= 1:
            return m
        mid = len(m) // 2
        left = m[:mid]
        right = m[mid:]

        left = merge_sort(left)
        right = merge_sort(right)

        if left[-1] > right[-1]:
            count += 1

        return merge(left, right)
    
    def merge(left, right):
        result = []
        
        while len(left) > 0 and len(right) > 0:    
            if left[0] <= right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        
        if len(left) > 0:
            result.extend(left)
        if len(right) > 0:
            result.extend(right)
        return result
    
    sorted_arr = merge_sort(arr)
    answer_1 = sorted_arr[N // 2]

    print(f"#{test_case} {answer_1} {count}")

이렇게 풀었는데 제한시간 초과가 나서 뭐가 문제인가 싶었다. pop(0) 함수의 연산이 O(N)의 복잡도를 가지고 있다고 해서, 이 부분을 고쳐줬다.

T = int(input())
for test_case in range(1, T+1):
    N = int(input())
    arr = list(map(int, input().split()))

    count = 0

    def merge_sort(m):
        global count

        if len(m) <= 1:
            return m
        mid = len(m) // 2
        left = m[:mid]
        right = m[mid:]

        left = merge_sort(left)
        right = merge_sort(right)

        if left[-1] > right[-1]:
            count += 1

        return merge(left, right)
    
    def merge(left, right):
        result = []
        i, j = 0, 0

        while i < len(left) and j < len(right):    
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        
        result.extend(left[i:])
        result.extend(right[j:])
        return result
    
    sorted_arr = merge_sort(arr)
    answer_1 = sorted_arr[N // 2]

    print(f"#{test_case} {answer_1} {count}")

병합 정렬 옛날부터 정말 많이 봤는데도 도저히 익숙해지지 않는다. 이건 응용의 응용 축에도 못 끼는데... 문제를 풀기 전에 병합 정렬, 퀵 정렬 알고리즘부터 제대로 외워놔야 할 것 같다.