1. 문제

---

출처: 백준 10989번 수 정렬하기 3

2. 풀이

---

수의 범위가 작다면 카운팅 정렬을 사용해 보라고 문제가 제시하고 있다.

문제에서 정렬할 수들의 최댓값이 10,000으로 주어졌고, 카운팅 정렬을 써보라고 하였으니 해당 알고리즘을 사용한다.

카운팅 정렬 (Counting Sort)

카운팅 정렬은 주어진 숫자 리스트에 각 숫자들이 몇 개씩 있는지를 저장하고, 이를 활용하여 정렬하는 방식이다. (왜 이 알고리즘만 번역을 하지 않고, 그대로 카운팅이라 했을까...)

먼저 정렬하려는 숫자들의 최댓값을 찾고, 그 값 크기만큼의 리스트를 생성한다. 그리고, 각 index의 숫자가 몇 개씩 있는지 카운팅하여 해당 리스트에 저장한다. (음수까지 있다면, 리스트의 index를 활용하는 방법을 바꿔야 할 것이다.)
이후에, 가장 낮은 index부터 개수가 0이 아닌 index의 숫자만큼 index를 출력해 주면 정렬이 가능해진다.

시간 복잡도 계산을 위해 전체 숫자의 개수를 $n$, 최댓값을 $k$라고 해보자.
$n$개의 숫자의 개수를 세는 과정에서 $n$, 개수를 세어놓은 리스트에서 숫자를 뽑는 과정에서 $k$가 소요되므로 시간 복잡도는 $O(n+k)$가 된다.
따라서 최댓값이 커지면 시간 복잡도가 다른 알고리즘에 비해 굉장히 커진다는 단점이 있지만, 값이 작을 때는 선형이기 때문에 큰 장점을 지닌다.

3. 소스코드

---

import sys
input = sys.stdin.readline

cnt = [0]*10001
N = int(input())

for _ in range(N):
    cnt[int(input())] += 1

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

4. 그 외

---

카운팅 정렬은 대학교 때 배운 기억이 딱히 없어서, 처음 봤을 때 이해하기 좀 어려웠다.
이걸로 정말 정렬이 되나 싶었는데, 이해하고 나니 꽤 신기한 느낌이었다.