[BOJ] 2751번: 수 정렬하기 2

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

2751번: 수 정렬하기 2

 

Python3

초기 코드

if __name__ == '__main__':
    N = int(input())
    numbers = []
    for _ in range(N):
        numbers.append(int(input()))
    numbers.sort()
    print(*numbers, sep="\n")

이전에 풀었던 정렬 문제와 유사하다고 생각했고 파이썬 내장함수인 sort()를 사용해 해결하려고 했다. 아무래도 N log N의 시간복잡도를 가지는 좋은 정렬 알고리즘이기 때문에 왠만하면 해당 함수를 사용하여 정렬을 해결한다.

하지만 위의 코드를 제출했을 때 결과는 "시간초과"였다. 

처음엔 정렬이 문제인가 했지만 N log N보다 좋은 알고리즘은 없기에 입력에서 잘못이 있음을 깨달았다. 바로 input() 함수!!  최대 1,000,000개의 숫자를 받을 수 있는 상황에서 이만큼 반복문을 돌리면서 input()함수로 받기에는 시간이 너무 오래걸렸던 것이다. 

input()의 경우 prompt message를 출력하고, 개행문자를 삭제한 값을 리턴하기 때문에 느리다. 따라서 sys 라이브러리의  sys.stdin.readline()함수를 사용했다. 이 함수는 prompt message를 인수로 받지도 않고 입력받은 문자열에 개행 문자를 포함되어 있는 상태로 리턴한다. 이를 깨달은 후 입력에 해당하는 코드를 바꾸었다.

 

최종 코드

import sys
if __name__ == '__main__':
    N = int(input())
    numbers = []
    for _ in range(N):
        numbers.append(int(sys.stdin.readline()))
    numbers.sort()
    print(*numbers, sep="\n")