[ SW Expert Academy ] 5204. 병합정렬

1차 시도. 시간초과 [ 0 / 10 ] Fail

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

def merge_sort(a):
    global answer

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

    left = merge_sort(left)
    right = merge_sort(right)
    if left[-1] > right[-1]:
        answer += 1
    return merge(left, right)

if __name__ == '__main__':
    T = int(input())
    for test_case in range(T):
        n = int(input())
        a = list(map(int, input().split()))
        answer = 0
        result = merge_sort(a)

        print("#"+str(test_case), result[n//2], answer)

 

 

2차 시도. [ 10 / 10 ] Pass.

1차 제출에서 왜 시간초과가 났는지 이유를 모르겠다 ㅠㅜㅠㅜㅠ 그냥 뜯어서 다시 하고서야 PASS처리됨... ㅠㅜ

아 진짜 속이 안 시원하다. ㅠㅜ

def merge(left, right):
    i, j = 0, 0
    sorted_list = []
    
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1
    while i < len(left):
        sorted_list.append(left[i])
        i += 1
    while j < len(right):
        sorted_list.append(right[j])
        j += 1
    return sorted_list

def merge_sort(a):
    global answer

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

    left = merge_sort(left)
    right = merge_sort(right)
    if left[-1] > right[-1]:
        answer += 1
    return merge(left, right)

if __name__ == '__main__':
    T = int(input())
    for test_case in range(1, T+1):
        n = int(input())
        a = list(map(int, input().split()))
        answer = 0
        result = merge_sort(a)

        print("#"+str(test_case), result[n//2], answer)