[백준] 10989번 : 수 정렬하기 3(JAVA)

오늘도 열심히 문제푸는 은구.gif

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

10989번: 수 정렬하기 3

위의 문제는 Baekjoon Online Judge의 단계별로 풀어보기 중 12단계

 

정렬의 카테고리에 포함되어 있는 문제이다.

 

카운팅정렬(계수 정렬)을 이용하여 풀어야 하는 문제이며

 

수의 범위가 작을 때 더욱 빠르게 정렬할 수 있는 방법이 계수 정렬이다.

 

처음에는 입력을 Scanner로 썼을 때는 시간초과가 났었다.

 

그래서 더 빠르게 입력하고 출력하는 방법인 Buffer방법을 쓰니 통과가 되었다.

 

알고리즘은 나중에 시간날 때 다시 정리해서 올려야겠다.

 

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 Number = Integer.parseInt(br.readLine());
		
		int[] Sort, f, Result;
		
		Sort = new int[Number];
		Result = new int[Number];
		f = new int[10001];
		
		
		for(int i = 0; i < Number; i++)
			Sort[i] = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < Number; i++)
			f[Sort[i]]++;
		
		for(int i = 1; i < 10001; i++)
			f[i] += f[i - 1];
		
		for(int i = Number - 1; i >= 0; i--)
			Result[--f[Sort[i]]] = Sort[i];
		
		for(int e : Result)
			bw.write(e + "\n");

		bw.flush();
		bw.close();
		br.close();
	}
}