[파이썬][백준] 2751번: 수 정렬하기 2

1. 문제

주소: https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

문제 유형: 정렬

 

• 총숫자의 개수는 1,000,000개이므로 for문이 2개 들어가는 버블, 선택, 삽입 정렬 등은 사용할 수 없음 (시간 초과)
• 시간 복잡도가 O(nlogn)인 퀵 정렬이나 병합 정렬을 이용
• 퀵 정렬을 이용할 시 메모리 초과가 되어 병합 정렬을 이용함

2. 소스코드

import sys


def mergesplit(num_list):
    if len(num_list) <= 1:
        return num_list

    mid = len(num_list) // 2
    left = mergesplit(num_list[:mid])
    right = mergesplit(num_list[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    left_index, right_index = 0, 0

    while len(left) > left_index and len(right) > right_index:
        if left[left_index] > right[right_index]:
            result.append(right[right_index])
            right_index += 1
        else:
            result.append(left[left_index])
            left_index += 1
    while len(left) > left_index:
        result.append(left[left_index])
        left_index += 1
    while len(right) > right_index:
        result.append(right[right_index])
        right_index += 1
    return result



n = int(sys.stdin.readline())
n_list = []
for _ in range(n):
    n_list.append(int(sys.stdin.readline()))

sorted_list = mergesplit(n_list)
for num in sorted_list:
    print(num)