[10989] 수 정렬하기3 (1 ≤ N ≤ 10,000,000, K≤10,000, 계수 정렬)

10989번: 수 정렬하기 3

 

분석

• N의 최대 개수가 10,000,000으로 매우 큼. 주어지는 숫자의 크기가 10,000보다 작은 자연수
• 계수 정렬의 시간복잡도 : O(kn)

수열 A :  5 2 3 1 4 2 3 5 1 7
count 배열

0	1	2	3	4	5	6	7	...	10001
0	2	2	2	1	2	0	1		0

풀이

"""
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
"""
import sys
input=sys.stdin.readline

n=int(input())
count=[0]*10001  # 카운팅 정렬 리스트

for i in range(n):
    count[int(input())]+=1

for i in range(10001):
    if count[i]!=0:
        for _ in range(count[i]):
            print(i)