백준 2751번 수 정렬하기2 - Python

문제

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

입력

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

출력

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

이 문제를 푸는데 구현 코드는 쉬웠지만 시간초과 발생하는 것에서 문제가 발생했습니다

테스트코드로 입력되는 값의 수가 많아지면 많아질수록 입력하는데 드는 시간이 오래 걸리게 됩니다

python에 Input()으로 받는 것도 백준 해당 문제에서는 시간을 많이 잡아먹게 되어 시간초과 발생을 유발합니다

그래서 할 수 있는 방법은 sys 모듈을 불러와서 sys 모듈 안에 있는 표준입출력 함수를 활용하는 것 입니다

sys.stdin.readline()은 파이썬에 기본 내장된 input()함수보다 훨씬 빠른 입력을  해줍니다

---

혹, sort()가 느려서 시간초과가 발생한게 아닐까 하는 생각이 들 수 있습니다만?

파이썬 내부에서 구현된 sort 알고리즘은 퀵소트 정렬이라서 전체리스트를 다 순회하지 않습니다

시간복잡도는 O(nlogn)이기 때문에 간단한 문제라면 파이썬 내부에 이미 만들어진 함수를 활용하는 것이 좋습니다

---

구현한 코드는 다음과 같습니다

import sys

N = int(input())
M = []
for i in range(N):
    M.append(int(sys.stdin.readline().strip()))

M.sort()
for i in M:
    print(i)
    
# readline을 사용하지 않았을 경우 -> 시간초과 발생
# N = int(input())
# M = [int(input()) for _ in range(N)]
# M.sort()
# print(M)