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

https://www.acmicpc.net/problem/10989

언뜻 보면 그냥 오름차순으로 정렬하라는 쉬운 문제처럼 보이지만, N의 최대 범위가 10,000,000으로 매우 큰 숫자이다. 따라서 우리가 흔히 정렬을 사용할때 걸리는 시간복잡도인 $O(nlogn)$을 사용할 수 없다!

따라서 여기서는 계수 정렬(Counting Sort)라는 조금 특수한 정렬을 사용해야 한다.

계수 정렬은 배열의 인덱스를 주어진 데이터의 값으로 활용하는 것이다. 배열의 최대길이인 k에 따라 시간복잡도가 결정되므로 $O(kn)$라고 할 수 있다.

주로 입력받은 데이터개수가 k보다 작을 경우 유용하게 사용하는 알고리즘이다.

예를 들어 우리가 입력한 배열의 값이 [1, 10000]이라고 한다면, 이 배열은 2개의 값만을 가지고 있음에도 불구하고 카운팅 배열의 크기는 입력값의 최대값인 10000으로 설정해 주어야 하며, 반복 연산 횟수도 배열의 최대길이인 10000까지 진행되므로 매우 비효율적일 수 있다는 것이다.

코드가 길지 않으므로 바로 확인해보면서 문제를 풀어보자.

import sys
input = sys.stdin.readline

# 문제에서 10,000보다 작거나 같은 자연수라고 주어짐
count = [0] * 10001
N = int(input())

for i in range(N):
    tmp = int(input())
    # 입력받은 값을 인덱스로 사용
    # 주어진 입력의 개수만큼 카운트
    count[tmp] += 1

for i in range(10001):
    if count[i] != 0:
    	# 카운트된 개수만큼 인덱스 값(입력 값) 출력
        for _ in range(count[i]):
            print(i)

자주 사용하진 않지만 이런 정렬도 있다는 점을 염두해 두면 좋을 것 같다.