백준 단계별로 풀어보기 - 정렬에서 상위 3개 문제가 수 정렬하기 문제이다. 1, 2번은 파이썬 정렬함수인 sort()를 이용하면 쉽게 통과할 수 있는데, 3번은 동일한 코드를 제출할 경우 메모리 초과 가 난다. 문제 소개에서도 계수 정렬을 이용하라고 하였으므로 계수 정렬에 대해 정리하고, 해당 알고리즘으로 푼 풀이를 작성하고자 한다.

---

계수 정렬(Counting Sort)

계수 정렬이란 말 그대로 숫자를 정렬할 때, 그 숫자가 등장하는 횟수를 이용하는 정렬방법이다.

1. 가장 작은 데이터와 가장 큰 데이터가 담길 수 있는 배열을 초기화 한다. (큰 데이터의 수에 맞춰 배열의 크기를 할당해준다.)
2. 등장 횟수를 기록할 배열을 count라고 한다면, count배열에 정렬되지 않은 배열의 수들의 등장 횟수를 기록한다.
3. count배열에 저장된 등장 횟수를 누적합으로 바꾼다. (누적합으로 바꾸면 자신이 몇번째 인덱스에 등장해야 되는지 알 수 있다.)
4. 이후 이를 이용하여 순서대로 숫자를 출력하면 정렬 끝

계수 정렬을 보기 쉬운 애니메이션으로 표현해주는 사이트가 있어서 링크 첨부한다! 👉Counting Sort
계수 정렬은 기본적으로 다음과 같은 조건에서만 사용이 가능하다.

1. 데이터는 양수여야 한다.
2. 데이터의 범위가 너무 크지 않아야 한다.(메모리 사이즈를 넘어서는 안된다.)

BOJ에서도 수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다. 라고 명시하고 있다. 해당 문제에서도 정렬할 수들은 10000이하의 자연수라는 조건을 걸어줬다.

계수 정렬 구현 (Python)

위에 기재한 정렬 방법에 따라서 파이썬으로 알고리즘을 구현해보자. BOJ문제에서 처럼 10000이하의 자연수들로 구성된 배열을 정렬한다고 하자.

numlist = [100, 9, 4, 45, 4, 10000, 123, 140, 9, 100]
count = [0] * 10001

# 누적합 구하기
for i in range(len(numlist)):
    count[numlist[i]] += 1

# 인덱스 데이터만 출력
for i in range(len(count)):
    for j in range(count[i]):
        print(i)

4
4
9
9
45
100
100
123
140
10000

짜잔
쉽게 정렬이 된다.

어차피 계수가 없는 수는 0이라서 반복문을 돌지 않는다.

계수 정렬의 시간복잡도

데이터의 개수를 N, 데이터의 최대값 크기를 K라고 할 때, 계수 정렬의 시간복잡도는 O(N+K)로 상당히 빠른 편에 속한다. 하지만 데이터의 최대값 크기만큼 배열을 할당해야하기 때문에 데이터의 최대값의 크기가 엄청나게 크다면 비효율적이다. 예를 들어서 [2, 10000, 3]이라는 배열을 정렬하기 위해서는 배열을 10000개나 초기화를 해야한다.. 따라서 BOJ의 문제가 말했던 것 처럼 수의 범위가 작을 때 계수정렬을 사용하는 것이 좋다.

📍 10989번: 수 정렬하기 3

그렇다면 계수 정렬을 이용해서 해당 문제를 풀어보도록 하자. 👉[BOJ] 10989번: 수 정렬하기 3

import sys

N = int(input())

count = [0] * 10001
for i in range(N):
    input_num = int(sys.stdin.readline())
    count[input_num] += 1

for i in range(len(count)):
    for j in range(count[i]):
        print(i)

야호