[백준/파이썬] 10989 - 수 정렬하기 3

문제 설명

풀이 전략

N의 범위가 $1\leq N\leq 10,000,000$ 으로 $O(NlogN)$의 알고리즘으로도 시간 초과가 발생한다. 입력으로 주어지는 자연수의 범위가 $1\leq K\leq 10,000$ 이므로 $O(N+K)$의 알고리즘인 계수 정렬을 이용하면 해결할 수 있다. 계수 정렬은 각 숫자를 배열의 인덱스로 가지고, 배열의 내용은 해당 숫자의 갯수를 배열을 생성해 정렬하는 방법이다.

코드

import sys
arr = [0] * 10001
n = int(sys.stdin.readline().rstrip())
for _ in range(n):
    arr[int(sys.stdin.readline().rstrip())] += 1
for i in range(1,len(arr)):
    for _ in range(arr[i]):
        print(i)