카운팅 정렬 / 계수 정렬 (Counting Sort)

카운팅 정렬 / 계수 정렬 (Counting Sort) 이란?

• 비교를 사용하지 않고 정수의 개수를 세어 정렬하는 알고리즘
• 정수의 값이 특정 범위 내에 존재할 때 매우 빠르게 동작한다.
• 시간 복잡도는 O(n + k)
  • n은 정렬할 원소 개수, k는 정렬 대상 값의 범위

---

사용 조건

• 정수 배열이어야 한다.
• 값의 범위(k)가 너무 크면 비효율적이다.
• 음수도 정렬 가능하지만 보정 작업 필요하다. (예: count[num - min]++)

---

정렬 방법

• 입력 배열에서 가장 큰 수(max)와 가장 작은 수(min)를 찾는다.
• 등장 횟수를 저장할 count[] 배열을 만든다. (크기: max - min + 1)
• 각 숫자의 등장 횟수를 세서 count[]에 저장한다.
• count[]에 저장된 값을 순서대로 읽어 정렬된 결과를 만든다.

 

예제

public class CountingSort {
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        
        // 1. 배열에서 최댓값과 최솟값 찾기
        int max = arr[0], min = arr[0];
        for (int num : arr) {
            if (num > max) max = num;
            if (num < min) min = num;
        }

        // 2. 카운트 배열 만들기
        int[] count = new int[max - min + 1];
        for (int num : arr) {
            count[num - min]++;
        }

        // 3. 카운트 배열을 이용해 원본 배열에 정렬된 값 넣기
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i]-- > 0) {
                arr[index++] = i + min;
            }
        }

        // 결과 출력
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

---

사용 예시

• 시험 점수(0~100)
• 나이 정렬
• 숫자 자릿수 내림차순 정렬
• 알파벳 정렬 (A~Z)

---

실전 문제 풀이

2751. 수 정렬하기 2의 세번째 풀이

[Silver V] 2751. 수 정렬하기 2