백준 2751번 : 수 정렬하기 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

 

🍃 시간초과 코드

N = int(input())

num_list = []

for _ in range(N):
    num = int(input())
    num_list.append(num)
    
num_list.sort()

for num in num_list:
    print(num)

🍃 이유

1. 테스트 케이스의 수 갯수가 100만까지 있기 때문 복잡도 N^2으로 하면 시간이 너무 오래걸림

2. sort() 함수 -> sorted() 함수

- 파이썬의 내장 정렬 함수 sort()는 일반적으로 효율적으로 동작하지만 최악의 경우에는 O(N^2)의 시간 복잡도를 가질 수 있음

- sorted() 함수는 TimSort 알고리즘을 사용하며 대부분의 상황에서 빠르게 동작한다.

3. int(input()) 대신 import sys → sys.stdin.readline() 사용

- \n 포함해서 인식 (input()은 \n 제거해야해서 시간 오래걸림)

 

🍃 수정한 코드

import sys

N = int(input())

num_list = []

for _ in range(N):
    num_list.append(int(sys.stdin.readline()))

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