Baekjoon 문제 풀기 (10989번 : 수 정렬하기 3) Java

10989번 : 수 정렬하기 3

1. 문제읽기

---

계수정렬(Counting sort) 문제

n의 범위가 10,000,000 까지이므로 시간복잡도가 O(N)의 정렬을 써야한다는 것을 알아냈다.
그러나 내가 알고 있는 정렬 중에 O(N)은 없어서 검색해봤는데, Counting Sort를 써야했다.
몇 번 이해하려고 했으나 실패했는데, 오늘은 시간을 좀 들인 결과 완벽히는 아니더라도 어느정도 이해할 수 있었다.

Counting Sort는 수의 범위만큼의 메모리를 필요로 하기 때문에 항상 좋은 알고리즘은 아니다.
그렇기 때문에 많은 수가 적은 범위로 있어야 하고, 또한 양수여야한다는 조건이 있다.
이 문제는 수가 10,000보다 작거나 같은 자연수로, 두 조건을 모두 만족한다.

2. 제출 코드

---

이해를 돕기 위해 기본적인 Counting Sort의 알고리즘을 따라 문제를 풀었다.
counting 배열은 실제로 카운팅을 하는 값의 범위이므로 0을 포함하지 않기 때문에(0인덱스를 사용하지 않음) 범위+1을 해주어야한다. (안해서 틀림)
기존 배열과 result 배열은 어차피 받는 수만큼 채워지므로 상관없다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        // 기존 배열 arr
        int[] arr = new int[n];
        // 카운팅할 배열 counting : 값의 범위+1
        int[] counting = new int[10001];
        // 정렬한 배열 result
        int[] result = new int[n];

        // arr 채우기
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(bf.readLine());
        }

        // counting 하기
        for(int i = 0; i < n; i++) {
            counting[arr[i]]++;  // 기존배열의 값을 인덱스로 가지는 값을 +1씩
        }

        // 누적합 해주기
        for(int i = 1; i < counting.length; i++) {
            counting[i] += counting[i-1];  // 기존 값이 어디까지 위치하는지 알기 위해
            // arr = {1,2,1}라고 쳤을 때, counting = {0,2,1} 
            // 누적합 해주기
            // counting = {0,2,3} -> 1이 2번째까지, 2가 3번째까지라는 뜻
        }

        // 정렬하기
        for(int i = arr.length-1; i >= 0; i--) {  // 안정적으로 정렬하려면 맨 뒤에서부터 하는게 좋음
            int value = arr[i];  // value = 기존 값
            counting[value]--;  // -1을 해줘야 result에 제대로 값이 들어감
            result[counting[value]] = value;  // result에 기존 값 넣기
        }
        StringBuilder sb = new StringBuilder();
        for(int i : result) {
            sb.append(i).append("\n");  // 출력
        }
        System.out.println(sb);
    }
}

3. 공부할 것

---

수의 범위를 알고 출력만 하는 상황이라면 counting 배열에 바로 값을 카운트해주고, 1부터 끝까지 for문을 돌면서 인덱스값을 출력해버리면(counting 배열의 모든 값이 0이 될 때 까지) 코드를 줄일 수 있다.
아래 예시처럼 말이다.

{1,2,1} 입력 -> counting = {0,2,1} -> 1 출력 -> counting = {0,1,1} -> 1 출력 -> counting = {0,0,1} -> 2 출력 -> counting = {0,0,0}

이걸 코드로 나타내면 아래와 같다.
확실히 시간이 2064ms에서 1640ms로 줄어들었다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int[] counting = new int[10001];

        // counting 하기
        for(int i = 0; i < n; i++) {
            counting[Integer.parseInt(bf.readLine())]++;
        }

        StringBuilder sb = new StringBuilder();
        // 정렬하기
        for(int i = 1; i < counting.length; i++) {
            while(counting[i] > 0) {
                sb.append(i).append("\n");
                counting[i]--;
            }
        }
        System.out.println(sb);
    }
}