[백준 10989] 수 정렬하기 3 (python 풀이)

1. 문제 

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

2. 입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

3. 출력

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

 

---

4. 포인트

1. 대략적으로 파이썬은 1초에 2000만번에 연산을 수행한다. 
   • 위와 같은 지표로 대략적으로 시간 복잡도를 계산하여 알고리즘을 선택할 수 있겠다
2.  input() 함수 보다는 sys.stdin.readline() 함수가 빠르다
3. 개수가 정해져있는 수 정렬에서는 계수 정렬 (counting sort ) 알고리즘을 사용 할 수 있다.
   • 시간복잡도 O(n) 을 갖는다.
   • 리스트의 sort() 함수의 시간 복잡도 O(nlogn) 인 점을 고려했을때 매우 빠름 

4. 문제 풀이

 해당 문제는 N이 천만 이하이므로 일반적인 정렬 의 시간복잡도 O(nlogn) 을 고려했을 때 시간 초과가 날 확률이 높다고 판단 했고 더 빠른 정렬 알고리즘중 계수 알고리즘을 찾을 수 있었다.

 계수 알고리즘은 리스트의 인덱스를 해당 수로 생각하고 value 에 그 수가 몇번 출연했는지를 저장한다. 시간복잡도 O(n) 을 갖게된다.  또한 sys 모듈을 통해 input을 받아 내 시간을 단축함으로써 문제를 해결 할 수 있다. 

 

# 수 정렬하기3

# 계수 정렬 알고리즘 사용

import sys
test = int(input())

lst = [0] * 10001

for i in range(test):
    val = int(sys.stdin.readline())
    lst[val] +=1



for i in range(10001):
    if lst[i] != 0 :
        for j in range(lst[i]):
            print (i)