[백준] 2751번 파이썬 (수 정렬하기 2)

1. 문제와 예제

문제

예제

sorted 함수를 사용하면 될 거 같은데 시간복잡도를 고려해봐야겠다.

---

2. 코드

import sys
input = sys.stdin.readline

N = int(input().rstrip())
lst = []

for _ in range(N):
    lst.append(int(input().rstrip())) # N개의 수를 list로 받음

for i in sorted(lst): # 정렬함과 동시에 출력
    print(i)

---

3. 풀이

문제에서 주어진 시간 제한은 2초이고 N의 최댓값은 100만이다. 시간 제한 안에 가능한지 알아보기 위해 sort, sorted의 시간복잡도를 알아보자. 이는 O(nlogn)보다도 최적화된 정도라고 한다. 또한 백준에서 1억 번의 연산이 1초가 걸린다고 생각하면 안전하다. 계산해보면 sort, sorted를 사용해도 되겠음을 판단할 수 있다.

 

또한 input() 대신 sys.stdin.readline()을 사용했다. input() 내장 함수는 parameter로 prompt message를 받을 수 있다. 따라서 입력받기 전 prompt message를 출력해야 하고 이는 약간의 부하로 작용할 수 있다. 따라서 100만 개나 입력값을 받을 수 있는 이 문제에서는 효율적으로 입력값을 받기 위해 sys.stdin.readline()을 사용했다.