[백준/JAVA] 10989: 수 정렬하기3

[백준/JAVA] 10989: 수 정렬하기3

Counting sort를 사용하여 정렬하는 문제이다.

• Counting sort란 배열에서 해당 숫자가 나온 개수를 세서 새로운 배열의 각 인덱스에 저장하고 그 갯수만큼 해당 숫자를 출력하는 정렬이다.

시간 복잡도는 O(n)이나 정확히는 O(n+k)이다. 시간 복잡도가 O(n)인 정렬이라니 굉장히 빠른 것처럼 보이기도 하지만 그렇지도 않다.

해당 문제에서는 n의 범위가 10000까지로 제한되어 있지만 개수(k의 범위)가 너무 많아지면 비효율적이게 되므로 상황에 따라 유의하며 사용해야 한다.

소스코드

---

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
    	BufferedReader br = 
        		new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = 
    			 new BufferedWriter(new OutputStreamWriter(System.out));
    	int n = Integer.parseInt(br.readLine());
    	int[] Counting = new int[10001];
    	
    	for(int i=0; i<n; i++)
    		Counting[Integer.parseInt(br.readLine())]++;

    	for(int i=1; i<Counting.length; i++) {
    		for(int j=0; j<Counting[i]; j++)
    			bw.write(i+"\n");
    	}
    	bw.flush();
    }
}