계수 정렬(Counting sort) 와 백준 10989

문제 링크

• 아주 쉬운 문제(쉬워 보이는)
• 그러나 Arrays.sort()로 풀게 되면 시간이 초과된다

계수 정렬이란?

표현 값의 범위가 명확히 제한되어 있을 때, O(N+K)의 시간 복잡도를 가지는 효율적인 정렬 알고리즘!

• 다른 정렬 알고리즘과 다르게 비교 기반이 아니다
• 입력값의 빈도수를 기반으로 정렬을 수행한다
• 최선, 평균, 최악의 경우 모두 O(N + K)의 시간 복잡도를 가지며, 여기서 N은 입력값의 개수이고 K는 입력값의 범위이다

---

자바로 구현한 계수 정렬

public class CountingSort {
    public static void countingSort(int[] arr) {
        // 입력값의 최대값을 찾기 (일반적으로 최대값이 주어져 있을 경우에 계수 정렬 사용 가능)
        int max = Arrays.stream(arr).max().getAsInt();

        // 빈도수 배열을 생성, 각 값의 빈도수를 계산
        int[] countArray = new int[max + 1];
        for (int num : arr) {
            countArray[num]++;
            // countArray 에, arr 에 존재하는 수의 인덱스를 ++
        }

        // 빈도수 배열을 순회하면서 정렬
        int index = 0;
        for (int i = 0; i < countArray.length; i++) {
            while (countArray[i] > 0) {
                arr[index++] = i;
                // 인덱스마다 적은 수 기준으로 계속 정렬
                countArray[i]--;
                // 중복이 있을 경우 1, 1, 1 이런식으로 계속 정렬됨
            }
        }


    }

순서대로 설명

1. 입력의 최댓값 찾기 ( 범위를 정해주기 위해서 )
2. 주어진 arr 를 돌면서, 어레이의 요소에 해당하는 "인덱스" 값을 countArray에서 올려준다.

• ex ) arr = {1,1,3,4,5} -> countArray = {0,2,0,1,1,1}
  위와같이 인덱스에 해당하는 값이 등장할때마다 +1

3. 인덱스 숫자를 선언해주고
4. countArray 를 작은 숫자부터 반복문 돌면서 카운트어레이에 해당 인덱스 값이 0 이상인 경우(등장했을 경우) 어레이의 인덱스에 i를 할당 후 증가, 카운트어레이의 해당값 감소

실제 출력은?

public static void main(String[] args) {
        int[] arr = {5, 3, 9, 1, 7, 5, 5, 7};

        // 계수 정렬
        countingSort(arr);
        // 출력
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

잘 정렬이 되는 모습!

---

문제의 풀이

 public class BOJ10989 {
       
        public static void main(String[] args) throws IOException {
            int[] cnt = new int[10001];

            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            int N = Integer.parseInt(br.readLine());

            for (int i = 0; i < N; i++) {
                cnt[Integer.parseInt(br.readLine())] ++;
            }

            br.close();

            StringBuilder sb = new StringBuilder();
            
            for(int i = 1; i < 10001; i++){
                while(cnt[i] > 0){
                    sb.append(i).append('\n');
                    cnt[i]--;
                }
            }
            System.out.println(sb);
        }
    }

• 이 문제가 거지같은 이유 : BuffeeredReader, StringBuilder 등 안쓰면 시간초과 남

---

기관지염은 대체 뭘까? 죽어가는 와중에 계수정렬을 남겨 본다.