[백준] 10989번 - 수 정렬하기 3

문제 분석

이 문제는 N의 최대 개수가 10,000,000으로 매우 크기 때문에 O(nlogn)보다 더 빠른 알고리즘이 필요하다.
문제에서 주어지는 숫자의 크기가 10,000보다 작다는 것을 바탕으로 기수정렬과 함께 많이 사용되는 계수 정렬(counting sort)을 사용하여 문제를 해결하면 된다.

정렬하는 데이터의 개수가 너무 많은 경우 기수 정렬 알고리즘을 활용하는 것이 좋을 때도 있다.

소스 코드

# 수 정렬하기3

import sys
input = sys.stdin.readline

arr = [0] * 10001
N = int(input())
for _ in range(N):
    arr[int(input())] += 1

for i in range(1, 10001):
    while arr[i] != 0:
        print(i)
        arr[i] -= 1