백준 10989번: 수 정렬하기 3(JAVA) / 계수 정렬(counting sort)

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

시간을 단축하기 위해 Scanner 대신 BufferedReader 사용하였고 출력도 StringBuilder를 사용하였다.

정렬로 계수정렬(counting sort)를 사용하였다

 

*Counting sort 시간복잡도: O(n) 

->10000보다 작거나 같은 자연수라고 했기 때문에 계수정렬을 사용할 수 있다. 

수를 입력받을 때마다 해당 숫자의 cnt값 1 증가시키면 1부터 10000까지 중복을 포함한 정렬을 할 수 있다.

 

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

public class Main {
	public static void main(String[] args) throws IOException{
   
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		int[] cnt = new int[10001];

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

		for(int i = 1; i <10001; i++){
			while(cnt[i]>0){
				sb.append(i+"\n");
                cnt[i]--;
            }
		}
		
		System.out.println(sb);	
	}
}