카운팅 정렬

문제

백준 2751

배경

해당 문제를 Arrays.sort() 를 사용해서 풀어보려고 했다가 수 많은 런타임 에러를 맞이하게 되었다.

찾아본 해결 방법

1. List<Integer> 안에 주어진 자료들을 넣고, Collections.sort() 를 사용

2. 카운팅 정렬을 사용해서 해결.
   --> 카운팅 정렬은 실제로 많이 사용하게 된다고 해서 이 글에선 이에 대해 알아볼 것이다.

카운팅 정렬이란?

카운팅 정렬은 수많은 정렬 알고리즘 중 시간복잡도가 𝚶(𝑛) 을 가진 알고리즘이다. 이게 가능한 이유는 카운팅 정렬은 직접적으로 값 들을 비교하지 않기 때문이다.

값 들을 직접 비교하는 대신에 주어진 숫자들을 인덱스로 하는 counting 배열을 새로 선언하게 된다.

가장 큰 단점으로는 counting 배열의 크기 == 주어진 숫자 중 가장 큰 값 이라는 점이다.
극단적인 경우로, arr={1,0,0,1000000} 라는 배열을 카운팅 정렬을 사용한다고 했을 떄
counting 배열의 크기는 1,000,000 일 것이고, 이는 단순히 4개의 숫자를 정렬하기 하는 거 치고는
메모리의 크기가 너무 크다는 것이다.

카운팅 정렬 구현

public class CountingSort {
    public static void main(String[] args) {
        int[] array = new int[100];     // 수열의 원소 : 100개
        int[] counting = new int[31];   // 수의 범위 : 0 ~ 30
        int[] result = new int[100];    // 정렬 될 배열

        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (Math.random() * 31);
        }

        // process 1
        for (int i = 0; i < array.length; i++) {
            counting[array[i]]++;
        }

        // process 2
        for (int i = 1; i < counting.length; i++) {
            // 누적합
            counting[i] += counting[i - 1];
        }

        // process 3
        for (int i = array.length - 1; i >= 0; i--) {
            /*
             * i 번째 원소를 인덱스로 하는 counting 배열을 1 감소시킨 뒤
             * counting 배열의 값을 인덱스로 하여 result 에 value 값을 저장한다
             */
            int value = array[i];
            counting[value]--;
            result[counting[value]] = value;
        }

        // 주어진 배열
        System.out.println("array[]");
        for (int i = 0; i < array.length; i++) {
            if (i % 10 == 0) System.out.println();
            System.out.print(array[i] + "\t");
        }
        System.out.println("\n\n");

        // 주어진 배열의 숫자들의 빈도를 나타내는 배열
        System.out.println("counting[]");
        for (int i = 0; i < counting.length; i++) {
            if (i % 10 == 0) System.out.println();
            System.out.print(counting[i] + "\t");
        }
        System.out.println("\n\n");

        // 정렬된 배열
        System.out.println("result[]");
        for (int i = 0; i < result.length; i++) {
            if (i % 10 == 0) System.out.println();
            System.out.print(result[i] + "\t");
        }
        System.out.println();
    }
}

문제 풀이에 적용

import java.io.*;

public class Prob_2751 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] arr = new int[2000001];       // 수의 범위 : -1,000,000 <= x <= 1,000,000 -> 2,000,001 개
        int n = Integer.parseInt(br.readLine());

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

        for (int i = 0; i < arr.length; i++) {
            while (arr[i]-- > 0) {
                System.out.print((i - 1000000) + "\n");
            }
        }
    }
}

문제처럼 만약 입출력만 하게 된다면, 위에 구현에서의 array, result 배열을 선언할 필요 없이 바로 counting 배열가지고 사용하면 된다.

참고

https://st-lab.tistory.com/104