[Java] 백준(브론즈-1) 10989번 - 수 정렬하기 3

입출력 예시

Input

10
5
2
3
1
4
2
3
5
1
7

Output

1
1
2
2
3
3
4
5
5
7

문제 풀이

---

문제에서 요구하는 시간제한은 3초이다.
Arrays.sort() 메소드를 이용해도 풀 수 있지만, 시간 제한은 마지노선으로 보인다.

그래서 정렬 알고리즘 중에서 O(n)으로 가장 빠른 시간복잡도를 가지는 카운팅 정렬(계수 정렬)로 풀어야 한다.
사실 문제 설명란에서 카운팅 정렬로 풀어야 한다고 친절히 설명해주었다.

먼저 카운팅 정렬이 무엇인지 알아보자.

카운팅 정렬(계수 정렬) 이란?
데이터의 값을 비교하여 데이터가 몇 번 나왔는지 세어 정렬하는 알고리즘이다.
정렬할 배열 최대값보다 1 큰 크기의 카운팅 배열을 생성해야 하는데 수의 범위가 클 수록, 메모리 낭비가 크기에 자주 사용하지 않는다.

본래 카운팅 정렬을 이용할 때, 아래 3가지 과정을 진행해야 하나, 본 문제에서는 정렬된 수를 출력만 하므로 간소화된 방식으로 풀어볼 예정이다.

1. 별도의 카운팅 배열에 주어진 수가 몇번 나왔는지 세어 저장한다.
2. 카운팅 배열의 값을 합배열(누적합) 형식으로 변환한다.
3. 주어진 수 중 마지막 수부터 순회하며 카운팅 배열의 각 값에서 -1한 인덱스 값이 정렬된 배열에 새 위치가 된다.

카운팅 정렬의 구체적인 메커니즘에 대해서는 여기를 참고하면 자세히 나와있다.

카운팅 정렬을 활용해 도출한 아이디어는 다음과 같다.

• 정렬된 수를 출력하면 되기 때문에 별도의 카운팅 배열을 생성하지 않는다.
• 주어진 수의 범위는 10,000보다 작거나 같은 자연수이기에 10,001 만큼의 크기를 가진 배열을 생성한다.
• 주어진 수들이 몇 번 나왔는지 카운팅 배열 인덱스에 세어 저장한다.
• 주어진 수의 범위만큼 반복하며 인덱스 값이 0이 될 때까지 인덱스 값을 출력한다.

이제 코드를 작성해보자.

int N = Integer.parseInt(br.readLine());
int[] arr = new int[10001];

N을 입력받고, 문제에서 요구한 수의 범위 +1 만큼의 arr 배열을 생성한다.

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

그리고 입력받는 수마다 arr 배열의 인덱스에 카운팅하여 저장한다.

for(int i=0; i<arr.length; i++) {
    while(arr[i] > 0) {
        bw.write(i+"\n");
        arr[i]--;
    }
}

마지막으로 현재 arr 배열의 값을 1씩 감소시키면서 해당 인덱스의 값이 0이 될 때까지 i값, 즉 인덱스를 출력해주면 된다.

실행결과

위 제출란이 Arrays.sort()를 이용한 풀이이고, 아래 제출란이 카운팅 정렬 풀이이다.
카운팅 정렬을 이용해서 푸는 것이 훨씬 빠르다는 것을 알 수 있었다.

작성코드

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
        int N = Integer.parseInt(br.readLine());
        
        int[] arr = new int[10001];

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

        for(int i=0; i<arr.length; i++) {
            while(arr[i] > 0) {
                bw.write(i+"\n");
                arr[i]--;
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

회고

• 정렬의 꽃인 카운팅 정렬에 대해서 공부할 수 있었고, 수의 범위가 작고 빠른 시간을 요할 땐 카운팅 정렬을 잘 활용해야 겠다고 느꼈다.