[JAVA]BOJ 10989, 수 정렬하기 3

counting sort와 bufferedReader, Writer를 사용한 문제이다. 정렬은 개념 자체는 단순하지만, 정렬 알고리즘의 종류도 많아서 구분하기 어렵다.. 게다가 어떤 문제에 어떤 정렬 알고리즘을 써야할지 헷갈린다. 시간복잡도도 계산해야 하기 때문에 ㅎㅎ 처음엔 merge sort로 풀었는데 계속 시간초과가 나더라..

 

counting sort 정리글 : https://noooodlefts.tistory.com/28

[Algorithm]Sort, 정렬(3)

 

이 문제는 직접 정렬을 할 필요가 없다. 숫자의 범위(10000이하)가 정해져있으므로 범위 내의 모든 숫자 수를 세면 된다. 그리고 1부터 개수를 저장한다. 

 

우선 10000칸의 int 배열을 생성한다

 

0   0   0   0   0   0   0   0   0   0    0     0      ...      0           0

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]   ...   [9999] [10000]

 

백준 예시인 5 2 3 1 4 2 3 5 1 7 를 입력받았다고 하자. 해당 입력값과 일치한 인덱스의 값을 증가시킨다.

 

1) 5입력

0   0   0   0   0   1   0   0   0   0    0     0      ...      0           0

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]   ...   [9999] [10000]

 

2) 2입력

0   0   1   0   0   1   0   0   0   0    0     0      ...      0           0

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]   ...   [9999] [10000]

 

3) 3입력

0   0   1   1   0   1   0   0   0   0    0     0      ...      0           0

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]   ...   [9999] [10000]

 

이런식으로 증가시키면 결과는

 

0   2   2   2   1   2   0   1   0   0    0     0      ...      0           0

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11]   ...   [9999] [10000]

 

이렇게 될 것이다. 그리고 arr[1]부터 인덱스 값을 출력한다. arr[i]를 출력하는 것이 아니라 i를 arr[i]번 출력해야 한다. 그러면 1 1 2 2 3 3 4 5 5 7 이 나올 것이다.

실제로는 정렬하지 않았지만 정렬한 결과와 같게 나온다. 시간복잡도는 O(n)으로 매우 효율적인 정렬 알고리즘이다.

import java.io.*;

public class BOJ10989 {
    // counting sort

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n, i, j, input;

        n = Integer.parseInt(bf.readLine()); // 개수 입력 받기

        int[] cnt = new int[10001]; // 개수에 맞춰 배열 생성

        // 입력값 카운트해서 배열에 저장
        for(i=0;i<n;i++){
//            input = Integer.parseInt(bf.readLine());
//            for(j=1;j<=n;j++)
//                if(input == j)
//                    cnt[j]++;
            cnt[Integer.parseInt(bf.readLine())]++; // 위에 코드와 같은 동작을 하지만, 훨씬 더 빠름
        }

        // 출력
        for(i=0;i<=10000;i++)
            for(j=0;j<cnt[i];j++)
                bw.write(i+"\n");
      	
      	bw.flush();
    }
}