[Python] Boj 백준 2751 수 정렬하기 2

문제

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

 

입력

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

 

출력

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

---

풀이

1. 수 정렬하기라 그냥 Python 내장함수 sorted사용. 당연함 안됨

2. 복잡도를 고민해 봄 -> quicksort를 통해서 코드 구현 -> 의외로 시간 초과

3. 그렇다면 mergesort -> 응 시간 초과

 

.. 어쩌.. 라는 걸까.. 하는 마음. 이거는 내가 2,3 에서 뭐 잘못했나 검색했더니.. 나온 코드는 매우 간결했다.

 

import sys

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

for i in sorted(num):
    print(i)

 

열심히 구글링한 결과 input()이 문제가 있었다.

input()은 코드에 사용된 sys.stdin.readline()보다 느린데, 그 이유는 prompt message를 출력하고 개행 문자를 삭제한 값을 리턴하기 때문이다.

근데 이걸 입력값이

1

2

3

이렇게 들어오니 당연히 반복문 안에 넣었고, 시간초과가 되는 아주 좋은 지름길이 되는 거였다.

그래서 input을 변경해주니 내장함수를 넣어서 사용해도 시간내에 결과를 얻을 수 있었다.