Counting Sort(계수 정렬)

백준 문제를 풀다가 계수 정렬에 대해 알게되었다. 상황에 따라서는 상당히 매력적인 배열 방식인 것 같다.

원리는 간단하다. A = [ 4, 5, 4, 6, 3, 3, 3, 1, 2, 7] 라는 리스트가 있을 때, 리스트를 차례대로 돌면서 해당 원소가 몇 번 나왔는지 체크하면 된다. 코드로 살펴보면 다음과 같다.

 

A = [ 4, 5, 4, 6, 3, 3, 3, 1, 2, 7] 
cnt = [0 for _ in range(8)]	# A에서 나올 수 있는 원소의 최댓값 + 1 

for a in A:
	cnt[a] += 1
    
print(cnt)
# [0, 1, 1, 3, 2, 1, 1, 1]

for i in range(1, 8):
    for _ in range(int(cnt[i])):
        print(i, end= ' ')
# 1 2 3 3 3 4 4 5 6 7

 

이렇게 리스트에 나오는 원소의 개수를 count한 다음 count한 수 만큼 해당 인덱스를 출력해주면 정렬이 완료된다. 

원소의 가능한 최댓값이 그렇게 크지 않는 이상 시간복잡도는 O(N)에 해당하기 때문에 효과적인 방식이라고 볼 수 있다. 

 

이 정렬방식의 단점으로는 리스트에 있는 최댓값을 알고 있어야 하고 이 값이 너무 크지 않아야 한다. 최댓값에 해당하는 길이만큼 count 배열을 만들어 놓아야 하기 때문에 자칫하면 심각한 메모리 낭비가 발생할 수 있다. (파이썬 딕셔너리를 사용하면 괜찮지 않을까 싶다.) 따라서 해당 정렬은 리스트 안 원소의 범위와 리스트의 길이를 종합적으로 고려해 선택해야 한다.

 

가장 대표적인 문제가 백준의 수 정렬하기 문제이다. 해당 문제에선 입력값의 수가 최대 10,000,000이고, 수의 범위는 10,000 이하의 자연수이기 때문에 오히려 계수 정렬을 사용하지 않을 때 메모리 초과가 발생한다. 따라서 정렬을 해야하는 리스트의 범위와 조건들을 잘 살펴보고 최적의 정렬 방식을 사용하는 능력을 키워야 할 것 같다. 

2022.06.14 - [ALGORITHM/BOJ] - 11989- 수 정렬하기

11989- 수 정렬하기