[백준] 10989 : 수 정렬하기 3 JAVA 풀이

카운팅정렬을 구현하는 방법은 다음과 같다.

 

1. 입력받을 숫자의 개수를 N이라고 했을 때,

   그 숫자들을 저장할 배열 arr[N]와 정렬된 값을 저장할 result[N]을 생성한다.

 

2. arr에 저장된 숫자들의 출현빈도를 저장할 배열을 생성하는데

   이때 그 배열의 크기는 입력되는 숫자의 범위로 한다.

   그 범위를 10000이하의 자연수라고 하면 count[10001]을 생성한다.

 

3. arr를 순회하면서 arr에 저장된 숫자의 출현빈도를

   count의 그 숫자를 인덱스로 하는 곳에 저장한다.

   count[arr[i]]++;

 

4. count 배열을 누적합으로 바꾼다.

   i=1부터 count.length-1까지 count[i] = count[i] + count[i-1];

   이를 수행하고 난 뒤의 count[0]이 3이고 count[1]이 4라면 count[2]는 7이다.

   이 값들은 arr배열에 0이 3개, 1이 1개 저장되어 있음을 의미한다.

   다시 말하면 배열의 인덱스는 0부터 시작하니

   count배열에 저장된 값-1은 정렬된 후 count배열의 인덱스값이 위치해야 할 자리가 된다.

 

5. result 배열에 정렬된 값을 저장한다.

   int val = arr[i];

   count[val]--; // count배열에 저장된 값-1

   result[count[val]] = val; 

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
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[] arr = new int[N];
        // 입력되는 수는 1~10000이니 count[1]부터 count[10001]까지 필요
        int[] count = new int[10001];
        int[] result = new int[N];
        
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        for(int i=0;i<arr.length;i++){
            count[arr[i]]++;
        }
        
        for(int i=1;i<count.length;i++){
            count[i] += count[i-1];
        }
        
        for(int i=arr.length-1;i>=0;i--){
            int val = arr[i];
            count[val]--;
            result[count[val]] = val;
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<result.length;i++){
            sb.append(result[i]).append('\n');
        }
        System.out.print(sb);
        
    }
}

딱 카운팅정렬의 정석대로 풀었는데 정렬된 값을 출력할 때

for(int val : result) System.out.println(val);

이렇게 했더니 시간초과가 나와서 스트링빌더로 바꿨더니 정답처리가 됐다.

 

https://st-lab.tistory.com/104

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

카운팅정렬 구현은 이 포스트를 참고했다!