알고리즘 풀이/백준

[백준][Java] 10989번 수 정렬하기 3

배게 2018. 5. 3. 02:55
728x90

카운터 정렬로 문제를 처리하였습니다.

감히 이론만 달랑 보고 풀 생각 절대 안하고

천천히 코드 카피해가면서 제 것으로 만들려고 노력했습니다.


*버퍼로 입력하고 출력해줘야 시간초과 안납니다.


참조 코드 : http://nhs0912.tistory.com/57

카운팅 정렬 애니메이션 : http://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.io.*;
import java.nio.Buffer;
import java.util.*;

public class Main {
	
	int[] numbers;
	int[] countArr;
	int[] result;
	
	int max = 0;
	int index = 0;
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	void inputNumbers() throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int size = Integer.parseInt(br.readLine().trim());
		numbers = new int[size];
		for(int i=0; i<numbers.length; i++) {
			int num = Integer.parseInt(br.readLine().trim());
			numbers[i] = num;
			if (max < num) max = num;
		}
	}
	
	void sort() throws IOException{
		inputNumbers();
		int maxNumber = max;
		countArr = new int[maxNumber +1];
		result = new int[numbers.length];
		
		for (int i=0; i<numbers.length; i++) {
			countArr[numbers[i]]++;
		}
		
		for (int i=1; i<countArr.length; i++) {
			countArr[i]+=countArr[i-1];
		}
		
		for (int i=numbers.length-1; i>=0; i--) {
			result[--countArr[numbers[i]]] = numbers[i];
			
		}
		for (int i=0; i<result.length; i++) {
			bw.write(result[i]+"\n");
		}
		bw.close();
		
		
	}
	
	public static void main(String[] args) throws IOException {
		new Main().sort();
		
	}
}