04. 카운팅 정렬(counting sort)

응용문제 : 백준 10989

 

카운팅 정렬(counting sort)란 데이터의 개수를 세어 정렬하는 방법이다.

시간복잡도는 O(N)으로 다른 정렬방법(quick sort, radix sort, etc.)보다 압도적으로 시간이 짧다.

하지만 데이터 값이 큰 경우에는 배열의 메모리 문제가 터질 수 있다는 단점이 있다.

(아래 백준 문제의 최대 데이터 값은 10,000이다.

이보단 작은 데이터 값을 최대로 가진 문제에 카운팅 정렬을 쓰는 걸 추천한다.)

 

직관적으로 카운팅 정렬을 보려면 3개의 array가 필요하다.

1. 정렬되지 않은(정렬해야 할) 데이터를 모은 array

2. (index=데이터 값) / 각 데이터 값(=index)의 개수를 입력한 array

3. 덧셈 처리한 2번 array의 각 값에 -1씩 뺀 값을 index로 한 array

 

counting sort를 모르고 3개의 array를 이해하긴 어려울 것 같다.

 

그림은 이 링크를 참고한다.

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

 

아래는 카운팅 정렬을 사용해 문제를 푼 코드

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

public class bronze10989 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int [] list = new int[10001];
		
		int count = Integer.parseInt(br.readLine());
		
		
		StringBuilder str = new StringBuilder();
		for (int i=0;i<count;i++) 
		{
			list[Integer.parseInt(br.readLine())]++;
		}
		
		for (int i=1;i<list.length;i++)
		{
			while(list[i] > 0) {
				str.append(i).append('\n');
				list[i]--;
			}
		}
		System.out.println(str);
	}
}