[SWEA] 병합 정렬

[SWEA] 병합 정렬

Problem URL : 병합 정렬

def merge_sort(arr):
    global ans
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] <= high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    if l < len(low_arr):
        merged_arr += low_arr[l:]
        ans += 1
    else:
        merged_arr += high_arr[h:]
    return merged_arr


T = int(input())


for tc in range(1, T + 1):
    N = int(input())
    ans = 0
    nums = list(map(int, input().split()))
    sorted_nums = merge_sort(nums)

    print("#{} {} {}".format(tc, sorted_nums[N//2], ans))

Comments

만약 코딩테스트에서 라이브러리를 사용못하게 한다면,
구현하기도 쉽고, 시간복잡도도 O(Nlog(N))인 병합정렬을 사용하도록 하자.