백준 정렬 - 10989번 : 수 정렬하기 3

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

10989번: 수 정렬하기 3

---

계수 정렬은 접해본 적이 없어서 검색을 통해 공부해가면서 구현했는데 시간복잡도가 무려 O(n)이라고 한다. 

하지만 숫자 범위만큼의 배열을 가지고 있어야 해서 비효율적인 부분이 존재한다고 한다.

이번에는 BufferedWriter를 이용해서 빠른 출력을 하려고 했는데도 시간초과가 떠서 Scanner보다 빠른 BufferReader를 사용하니 통과되었다.

import java.io.*;
public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
        for(int i=0; i<n; i++){
            a[i] = Integer.parseInt(br.readLine());
        }
        br.close();
        int[] range = new int[10001];
        for(int i=0; i<n; i++) {
        	range[a[i]]++;
        }
        for(int i=1; i<range.length; i++) {
        	range[i] +=range[i-1];
        }
        int[] ans = new int[n];
        for(int i=0; i<n; i++) {
        	range[a[i]]--;
        	ans[range[a[i]]] = a[i];
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=0; i<n; i++) {bw.write(ans[i]+"\n");}
        bw.close();
    }
	
}