백준 2751번: 수 정렬하기 2(Python)

수 정렬하기 2 

 

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

5
5
4
3
2
1

예제 출력 1 복사

1
2
3
4
5

 

코드

import sys
n = int(input())
num_list=[]
for i in range(n):
    num_list.append(int(sys.stdin.readline()))
num_list.sort()
for i in range(n):
    print(num_list[i])

우선, 이 문제는 전에 풀었던 백준 2750번 문제와 매우 유사하지만, N의 조건에서 최대값이 1,000,000으로 매우 커졌다...!

따라서 그 때의 코드를 그대로 쓴다면 시간 초과가 떠버리는 슬픈 일이 일어난다.

 

우선 정렬방법은 *파이썬의 내장함수를 사용하였기 때문에 정렬방법 말고 1,000,000개의 수를 입력받는 방법에서 차이를 두어야 한다. 

 

기존의 input()은 인자로 prompt message를 받을 수 있는 기능이 있다. 이 기능은 입력량이 크지 않다면 별 상관 없지만, 입력이 많아진다면 점점 쌓여 prompt message기능이 없는 sys.stdin.readline()과 시간에서 큰 차이가 나게 되는 것이다.

 

* 파이썬의 정렬 내장함수는 Timsort 알고리즘을 사용한다. Timsort 알고리즘은 Insert sort와 Merge sort를 결합하여 만든 최선 시간복잡도 O(n), 평균과 최악은 O(nlogn)의 시간복잡도를 보여주는 효율적인 알고리즘이기 때문에 개선하기 힘들다.