[Python] Baekjoon - 2751. 수 정렬하기 2

백준 2751번 수 정렬하기 2 문제는 N개의 중복되지 않은 숫자들을 정렬하는 문제이다. N의 범위가 넓기 때문에 시간 초과를 염두하고 풀어야 한다. 퀵 정렬을 이용하면 최악의 경우로 시간이 초과될 수 있으므로 항상 시간 복잡도가 일정한 병합 정렬을 사용하는 것이 좋다.

 

백준 2751번 수 정렬하기 2 문제 정보

알고리즘 분류

- 정렬

난이도

- 실버 5

 

수 정렬하기 문제 요약

N개의 중복되지 않은 숫자들이 주어졌을 때, 이를 정렬하여 출력하는 문제다. 여기서 N의 범위는 1 이상 1,000,000이하이다.

 

문제 풀이 과정

• 처음에는 퀵 소트를 짜서 제출했으나 시간이 초과되었다. 최악의 경우에 시간 복잡도가 커지기 때문인 것 같다. 따라서 시간 복잡도가 항상 일정한 병합 정렬을 이용하였다.
• merge 과정에서 매번 tmp 배열을 선언하는 것보다 전역 변수로 크기가 큰 tmp 배열을 미리 생성해놓는 것이 메모리, 속도 모두 향상된다.
• Python3로 통과하기 매우 어렵다고 하여 PyPy3로 제출

 

코드

import sys

N = int(input())
num_list = []
tmp = [0 for _ in range(N)]
for _ in range(N):
    num_list.append(int(sys.stdin.readline().strip()))


def merge_sort():
    def sort(left, right):
        if right - left < 2:
            return

        mid = (left + right) // 2
        sort(left, mid)
        sort(mid, right)
        merge(left, mid, right)

    def merge(left, mid, right):
        global tmp
        i, j = left, mid
        idx = 0

        while i < mid and j < right:
            if num_list[i] < num_list[j]:
                tmp[idx] = num_list[i]
                i += 1
                idx += 1
            else:
                tmp[idx] = num_list[j]
                j += 1
                idx += 1

        while i < mid:
            tmp[idx] = num_list[i]
            i += 1
            idx += 1

        while j < right:
            tmp[idx] = num_list[j]
            j += 1
            idx += 1

        for k in range(left, right):
            num_list[k] = tmp[k-left]

    sort(0, len(num_list))


merge_sort()
for x in num_list:
    sys.stdout.write(str(x) + '\n')