백준 10989 <수 정렬하기 3>

10989번: 수 정렬하기 3 (acmicpc.net)

10989번: 수 정렬하기 3

수의 개수의 범위가 상당히 크다. 천만개.. 일단 시간복잡도를 고려하면 O(NlogN)을 사용해야할 생각을하겠다.

 

이 문제의 경우 하지만 더 좋은 시간복잡도를 활용할수있는 정렬 알고리즘이 있는데 바로 카운팅 정렬이다.

카운팅 정렬은 일반적으로 이 문제와 같이 input받는 정수의 범위가 주어질때 유용하다.

시간복잡도는 O(N+K)이지만. 이상적으로 웬만하면 O(N)에 수렴한다.

즉 상당히 효율적인 정렬이라고 할 수 있다. 또한 코드도 상당히 간단하다.

 

일단 정수의 범위 중 max int의 크기를 갖는 배열을 하나 선언한다. 그렇다면 k개의 index를 지닌 배열 한개가 생성될것이다. 이후 정수가 입력되면 그 정수번째 인덱스의 값을 하나씩 올린다.

예를 들어 1 1 2 3 이 입력된다면

1번째 인덱스 값 = 2

2번째 인덱스 값 = 1

3번째 인덱스 값 = 1

이렇게 설정될 것이다.

 

이제 k번 for문을 돌며 1번째 인덱스값부터 차례대로 출력하면 input 값이 어지럽게 들어와도 배열 자체의 인덱스가 순서를 보장하기에 매우 쉽게 정렬하여 출력할수있다.

 

package 정렬알고리즘;

import java.io.*;

//운팅 정렬(Counting Sort)은 정수 배열을 정렬하는 비교 없이 선형 시간에 수행되는 안정적인 정렬 알고리즘입니다
// 알고리즘은 입력 배열의 범위가 제한되어 있을 때 특히 유용합니다
public class 카운팅정렬 {

	public static void main(String[] args) throws IOException {
		int[] range = new int[10001];
		 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < N; i++) {
            // 해당 인덱스의 값을 1 증가
            range[Integer.parseInt(br.readLine())] ++;
        }
 
        br.close();
 
        StringBuilder sb = new StringBuilder();
 
        // 0은 입력범위에서 없으므로 1부터 시작
        for(int i = 1; i < 10001; i++){
            // i 값이 개수가 0 이 될 때 까지 출력 (빈도수를 의미)
            while(range[i] > 0){
                sb.append(i).append('\n');
                range[i]--;
            }
        }
        System.out.println(sb);
		

	}

}