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

 

---

설명

이 문제는 숫자들을 오름차순으로 정렬하는 문제이다. 정렬하는데 있어 문제가 N의 범위가 100만까지 가기 때문에 시간복잡도가 중요한 문제이다. 시간복잡도가 O(N²) 인 정렬은 사용할 수 없다. 

여기서 O(NlogN) 인 고급 정렬 알고리즘(병합 정렬, 퀵 정렬, 힙 정렬)을 이용하거나 기본 정렬 라이브러리를 사용하는 방법이 있다. ( ※ 파이썬의 기본 정렬함수 ( sort(), sorted() ) 는 퀵 정렬로 되어있다. )

 

 

소스코드

import sys

N = int(input())

list = [int(sys.stdin.readline()) for _ in range(N)]

list.sort()
for val in list :
    sys.stdout.write(str(val)+'\n')

 

해설

• 파이썬의 기본 정렬 함수가 O(NlogN) 으로 잘 구성되어있어서 다른 정렬 방법을 사용할 필요가 없다고 생각하고 풀었습니다.
• 하지만 이번 문제에서는 시간이 중요해서 input() 과 print() 함수를 사용하면 시간초과가 발생하기 때문에 사용하지 않고 system input 과 system output을 사용하여 해결하였습니다.