[알고리즘] 계수 정렬 (Counting sort) 개념 + 백준 10989번 예제

💡 👍🏻 Counting Sort 는 데이터를 서로 비교하는 정렬 알고리즘과 다르게, 데이터의 값을 카운팅하여 정렬하는 알고리즘이다. 쉽게 말하면 배열에 있는 값의 수를 카운팅해서 자리 찾아주는 알고리즘임. (내가 이해하기로 그럼)

• ✨ 카운팅 소트의 시간 복잡도는 O(n)
• 일반적인 정렬들의 알고리즘 시간 복잡도가 O(nlogn)인 것을 생각하면 속도가 매우 빠르다.
• 하지만, 수의 범위가 커지면 메모리를 많이 낭비하기 때문에 자주 사용하지 않는다.

 

카운팅 소트 원리

1. 배열에서 max 값을 찾는다.
2. 카운팅 배열 (max 값+1) 과 결과 배열 b 를 생성한다.
3. 정렬할 배열의 값을 인덱스로 카운팅 배열에 카운팅한다 (counting++);
4. 카운팅 배열을 직전 요소 더한 값으로 다시 저장한다.
5. 정렬할 배열 값으로 카운팅 배열에서 자리 index 를 찾고, (--)한 자리 index 를 가지고 결과 배열에 정렬할 값을 저장한다. 사용한 카운팅 배열 값은 -1 해준다.

카운팅 소트 예시

먼저 정렬할 배열 준비.

int [] arr = {4, 5, 3, 4};

 

배열의 데이터의 최댓값의 +1 크기의 카운팅 배열 생성

int [] counting = new int[6];
for ( int i = 0; i < arr.length; i++ ) {
		counting[arr[i]]++; 
}

// counting[4] = 1;
// counting[5] = 1;
// counting[3] = 1;
// counting[4] = 2; //+1씩 늘어남 

counting = {0, 0, 0, 1, 2, 1}

 

카운팅 배열의 값을 누적합으로 바꾼다.

for ( int i = 1; i < counting.length; i++ ) {
	counting[i] += counting[i-1]; //직전 값 더하기 ~  
}

// counting[1] += counting[0]; -> {0, 0, 0, 1, 2, 1}
// counting[2] += counting[1]; -> {0, 0, 0, 1, 2, 1}
// counting[3] += counting[1]; -> {0, 0, 0, 1, 2, 1}
// counting[4] += counting[2]; -> {0, 0, 0, 1, 3, 1}
// counting[5] += counting[3]; -> {0, 0, 0, 1, 3, 4}

 

카운팅 배열에 저장된 (--)값을 시작 값으로 생각해서 정렬할 값을 넣어주면 끝!

int [] arr = {4, 5, 3, 4};
counting = {0, 0, 0, 1, 3, 4}
int [] result = { , , , };

// -------------------------- 역순으로 값을 찾는다. 

// if = 4 
--counting[4] => --3 //2 로 변경
result[2] = 4 (3번째 자리에 4)
// result = { , , 4, }
// counting = {0, 0, 0, 1, 2, 4}

// if = 3
--counting[3] => --1 //0 
result[0] = 3 (0번째 자리에 3)
// result = { 3, , 4, }
// counting = {0, 0, 0, 0, 2, 4}

// if = 5
--counting[5] => --4 //3
result[3] = 5 (3번째 자리에 5)
// result = { 3, , 4, 5}
// counting = {0, 0, 0, 0, 2, 3}

// if = 4
--counting[4] => --2 //1
result[1] = 4 (1번째 자리에 4)
// result = { 3, 4, 4, 5}
// counting = {0, 0, 0, 0, 1, 3}

** 결과 
result = {3, 4, 4, 5}

 

예제 - 백준 10989번 (수 정렬하기3)

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * 10989번 풀이 - 수 정렬하기 3
 * 카운팅 소트 !
 *
**/
public class Main13 {

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int [] arr = new int[n];
        int [] result = new int[n];

        int max = -1;

        for ( int i =0; i < n; i++ ){
            arr[i] = Integer.parseInt(br.readLine());
            if (arr[i] > max){
                max = arr[i];
            }
        }

        //소트용 카운팅 배열(max+1)에 카운팅
        int [] sorted = new int[max+1];

        for ( int i =0; i < arr.length; i++ ){
            sorted[arr[i]]++;
        }

        //누적합 구하기
        for ( int i =1; i < sorted.length; i++ ){
            sorted[i] += sorted[i-1];
        }

        //결과 배열 생성 및 값 찾아 넣기
        //역순으로 가져오기.
        //그 값으로 --counting 자리번호 찾음
        for ( int i = arr.length - 1; i >= 0; i-- ){
            int num = arr[i];
            result[--sorted[num]] = num;
        }

        StringBuilder sb = new StringBuilder();

        for ( int i = 0; i < result.length; i++ ){
            sb.append(result[i]+"\n");
        }

        System.out.println(sb.toString());
    }
}