[Problem Solving/Java] 백준 10989번 - 수 정렬하기 3

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

첫 번째 시도

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

public 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 a = Integer.parseInt(br.readLine());
        int[] array = new int[a];
        for (int i = 0; i < a; i++) {
            array[i] = Integer.parseInt(br.readLine());
        }
        int[] counting = new int[10001];    // 수의 범위 : 1 ~ 10000 
        int[] result = new int[a];    // 정렬 될 배열  
    // Counting Sort 
    // 과정 1  
        for (int i = 0; i < array.length; i++) {
            // array 의 value 값을 index 로 하는 counting 배열 값 1 증가  
            counting[array[i]]++;
        }
    // 과정 2  
        for (int i = 1; i < counting.length; i++) {
            // 누적 합 해주기  
            counting[i] += counting[i - 1];
        }
    // 과정 3 
        for (int i = array.length - 1; i >= 0; i--) {
            /*
             *  i 번쨰 원소를 인덱스로 하는 counting 배열을 1 감소시킨 뒤
             *  counting 배열의 값을 인덱스로 하여 result에 value 값을 저장한다.
             */
            int value = array[i];
            counting[value]--;
            result[counting[value]] = value;
        }

    // 정렬된 배열 
        for (int i = 0; i < result.length; i++) {
            bw.write(result[i] + "\n");
        }
        bw.flush();
        bw.close();
    }
}

해결 방법

문제에서 counting 정렬 사용을 권장했다. 그래서 counting 정렬을 검색해서 공부하고 코드를 참고해서 작성했다.

초기에 주어진 값들을 넣을 array 배열과 숫자 별로 나온 횟수를 저장할 counting 배열, array를 정렬해서 출력할 result 배열을 선언한다. array 배열과 result 배열의 크기는 같다. Counting 배열은 나오는 숫자를 모두 셀 수 있어야 하므로, 문제에서 주어진 수의 범위의 크기를 가지므로 크기가 10000이다.

과정 1에서는 array 배열에 들어있는 값을 인덱스로 하는 counting 배열의 값을 증가시킨다.

counting[array[i]]++;

위 문장을 통해 counting배열의 값을 1 증가시킨다.

과정 2에서는 counting배열의 값을 누적 합 하는 연산을 한다. 예를 들면 Counting[3]=counting[2]+counting[3]이다. 일반식으로 나타내면 아래와 같다.

counting[i] += counting[i - 1];

과정 3에서는 array 배열의 가장 마지막 인덱스에서 시작한다. I 번째 원소를 인덱스로 하는 counting 배열을 1 감소시킨 뒤 counting 배열의 값을 인덱스로 하는 result 배열에 array에서 가져온 원소를 저장한다. 코드는 아래와 같다.

for(int i = array.length - 1; i >= 0; i--) { 

int value = array[i]; 

counting[value]--; 

result[counting[value]] = value; 

}

마지막으로 정렬된 배열 result를 출력한다.

어려웠던 점 / 고쳐야할 점

정렬된 배열을 출력할 때 System.out.println을 썼더니 시간초과 오류가 나서 BufferedWriter로 썼다.