[Java] 카운팅 정렬

백준 10989번 문제를 풀 때, 그냥 Arrays.sort()를 이용해서  문제를 풀었었다.

이후에 다른 사람들이 어떻게 풀었나 찾아보고 카운팅 정렬을 이용해 문제풀이를 다시 하게 되었다.

Arrays.sort()와 BuffedReader등을 사용했을 때 메모리 345476KB, 시간이 2616ms 걸렸었는데

카운팅 정렬을 이용해서 문제풀이를 하니까 메모리와 시간 모두가 줄어들었다.

 

 

처음에 카운팅 정렬이 뭔지 몰라서 이해하는데 시간이 좀 걸렸어서 !

까먹기 전에 정리해두려고 한다.

 

카운팅 정렬은 데이터의 값이 몇 번 나왔는지를 세주는 것이다. 

 

문제로 이해하면 

5, 2, 3, 1, 4, 2, 3, 5, 1, 7 이 입력으로 들어올 때,

int[] arr = new int[10001]; // 주어지는 수들이 10,000보다 작거나 같은 수 이므로 배열의 크기를 10001로 지정

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

 

arr[5]++; arr[2]++; 이런식으로 증가시켜주는데, 이 반복문이 끝나면

arr[5]에는 입력들 중 5가 나온 횟수가 카운팅 되는 것이다. 

따라서 arr배열에는 각 index가 몇번 나왔는지가 값으로 들어있게된다.

 

이후에 

for(int i = 1; i <10001; i++) {
	while(arr[i] > 0) {
    	bw.wrtie(i+"\n");
        arr[i]--;
    }
}

 

for문이 1부터 돌기 때문에 오름차순으로 정렬이 되어 출력되고,

arr[i]가 0보다 크다는 것은 입력을 받은 것이기 때문에 출력하고 

입력된 수가 한번 나온 것이 아니라 여러 번 (1이 2번 입력) 나왔을 수 있기 때문에 arr[i]--; 를 해주며 while문 안에서 출력해준다

그러면 정렬을 쉽게 할 수 있다 ! 

 

카운팅 정렬은 시간복잡도가 O(n)이지만, 수의 범위에 따라 배열을 생성해줘야하기 때문에 메모리가 낭비될 가능성이 있다. 

그래서 수의 범위가 크지 않을 때만 사용을 하는 것이 좋다 ! 

 

그래도 .. 이 문제를 풀고나서 다른 문제를 풀 때, 배열에서 몇번 나왔는지 세고 싶을 때 카운팅 방식을 이용했다.

백준 17299 문젠데, 몇번 등장했는지 횟수에 대한 배열을 만들 때 다음과 같은 방식을 활용했다. 

 

int[] arr = new int[n];
int[] freq = new int[1000001];

StringTokenizer st = new StringTokenizer(br.readLine(), " ");

for(int i = 0; i < n; i++) {
	arr[i] = Integer.parseInt(st.nextToken());
	freq[arr[i]]++; // 이렇게 사용 !
}