[알고리즘] 카운팅 소트 (Counting Sort) 원리와 구현

👉🏾 원리 🌼

주어진 값들 사이의 범위가 작을수록 빠른 알고리즘이다.

주어진 배열이 있다. 미리 count라는 배열을 생성한다. 그리고 주어진 배열의 길이만큼 for loop를 돌면서 count 배열의 주어진 값 번째 자리를 1 더해준다. 그후 count 배열을 0부터 주어진 배열의 끝 인덱스까지 loop를 돌면서 count 배열의 n번째 자리에 저장된 수만큼 반복해서 출력해주면 된다. 잘 이해가 안간다면 코드로 보자!

 

👉🏾 문제점 ⚠️

주어진 값들 사이의 범위가 작을수록 빠른 알고리즘이지만 만약 주어진 값들이 [1,1000000, ...] 이라면 1과 1000000 사이의 의미 없는 999999개의 인덱스들을 전부 탐색해야 하기 때문에 주어진 값 사이의 범위가 클수록 느리다.

👉🏾 구현  💻

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

public class CountingSort {
    public static void main(String[] args) throws IOException {
    	// Scanner보다 빠른 입력 클레스
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        // 문자열 더하기를 지원하는 클레스
        StringBuilder sb = new StringBuilder();	

        int N = Integer.parseInt(bf.readLine());
	
        int[] count = new int[1000000000];
        int[] arr = new int[N];
        int max = 0;
        for(int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(bf.readLine());
            max = Math.max(max, arr[i]);
        }

        for(int n : arr) count[n]++;

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

        System.out.println(sb);
    }
}

 

StringBuilder가 생소하다면!! 👇🏾 

[☕️Java] StringBuilder 사용하는 이유와 사용법

BufferedReader가 생소하다면!! 👇🏾

업로드 예정

 

관련 백준 문제 👇🏾

2108번: 통계학