백준 10989. 수 정렬하기 3(JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String[] arge) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int num = Integer.parseInt(br.readLine());
		int[] arr = new int[num]; // 입력받을 배열
		int[] counting = new int[10001]; // 수의 범위
		int[] result = new int[num]; // 출력할 결과 배열
		
		for(int i = 0 ; i < arr.length; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		for(int i = 0 ; i < arr.length; i++) {
			counting[arr[i]]++;
		}
		
		for(int i = 1 ; i < counting.length; i++) {
			counting[i] += counting[i - 1];  
		}
		
		for(int i = arr.length -1 ; i >= 0 ; i--) {
			int value = arr[i];
			counting[value]--;
			result[counting[value]] = value;
		}
		
		for(int n : result) {
			sb.append(n).append('\n');
		}
		
		System.out.println(sb);
	}
}

 

자바 [JAVA] - 카운팅 정렬 (Counting Sort / 계수 정렬)

↑ 카운팅 정렬에 잘 설명을 해주셨기 때문에 먼저 위 글을 보면 이해하는데 도움이 될 것이다.

○ 문제 요약

카운팅 정렬(Counting Sort)로 입력받은 수를 정렬하여 출력해라. 

○ 문제 풀이

예제 입력 1을 기준으로 설명하겠다.

---

※ arr배열의 값이 아래 테이블과 같이 들어있다.

0	1	2	3	4	5	6	7	8	9
5	2	3	1	4	2	3	5	1	7

---

※ arr[0]부터 arr[9]까지 값을 counting[arr[i]]++에 넣어주면 아래 테이블과 같다. 

index	1	2	3	4	5	7
value	2	2	2	1	2	1

---

※ 위 테이블을 counting[i] += counting[i-1]을 해주면 아래 테이블의 모습을 보여준다.

숫자	1	2	3	4	5	7
누적합	2	4	6	7	9	10

여기서 누적합을 해준 이유는 count를 result에 넣어줄 때, 누적합의 값이 result의 인덱스 역할을 하도록 하기 위해서이다.

---

arr의 마지막 index부터 한 이유는 안정적으로 정렬을 하기 위해서이다.

 

for(int i = 10 -1 ; i >= 0 ; i--){

 int value = arr[9];

 counting[7]--; >> counting[7] = 10 이기 때문에 증감 연산자로 값을 -1 하면 9가 되는데 그 값이 result의 인덱스로 들어간다.

 result[9] = 7; >> result[9]에 7이 들어간다.

}

 

.....

중략

......

 

for(int i = 0 ; i >= 0; i--){

 int value = arr[0];

 counting[5]--;

 result[7] = 5

}

---

최종적으로 result 배열에 아래같이 정렬이 된 상태로 값이 들어있는 것을 알 수 있다.

0	1	2	3	4	5	6	7	8	9
1	1	2	2	3	3	4	5	5	7

StringBuilder를 이용해 값을 출력하면 원하는 대로 값이 나온다. 

○ 결과