[백준/Java] 문제 10989 - 수 정렬하기 3

문제

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

 

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다.

이 수는 10,000보다 작거나 같은 자연수이다.

 

 

출력

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

 

 

---

풀이

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

public class Main {
    public static void main(String[] args) throws Exception {
        // 카운팅 정렬 => 입력받을 숫자의 최소~최대 범위를 알고 있을 때 사용하면 빠른 성능을 기대할 수 있음.
        // 입력받을 수의 범위 : 1 ~ 10000
        int[] arr = new int[10001];
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int i=0; i < cnt; i++) {
            //입력받은 숫자에 해당하는 인덱스 공간에 +1을 시켜준다.
            //ex) 7 입력 => arr[7] = arr[7]+1;
            arr[Integer.parseInt(br.readLine())] ++;
        }

        br.close();

        StringBuilder sb = new StringBuilder();

        //0은 입력 안받음.
        for(int i = 1; i <= 10000; i++){
            // arr[i]의 수만큼 i 값을 출력한다.
            while(arr[i] > 0){
                sb.append(i).append('\n');
                arr[i]--;
            }
        }
        System.out.println(sb);
    }
}

 

우선, 이번 문제를 풀 때는 BufferedReader와 카운팅 정렬 알고리즘을 사용했다.

 

10989번 문제는 다른 정렬 문제와는 다르게, 시간 제한과 메모리 제한이 빡빡하게 걸려 있었다.

그만큼 메모리/동작속도 측면에서 높은 효율을 보여주는 알고리즘을 구현할 수 있어야 한다는 것..

 

솔직히, 2750번 문제에서 사용했던 선택정렬이나, Arrays.sort()를 제외하고는 높은 효율의 정렬을 어떻게 구현해야 할 지 감이 전혀 안잡혀서 문제를 구글링 해보았고, 아래 링크의 블로그 글을 참고하여 문제를 풀어보고 공부해봤다.

 

코드 및 설명 출처 : https://st-lab.tistory.com/107

[백준] 10989번 : 수 정렬하기 3 - JAVA [자바]

(설명을 정말 깔끔하게 잘 해놓으셨다.)

---

문제점 1) 시간 복잡도

문제 2750번에서 사용했던 선택 정렬 알고리즘의 시간 복잡도는 Θ(n²) 이다.

따라서 입력받을 수 있는 숫자의 갯수가 최대 10,000개인 지금 상황에서는 동작 시간이 너무 길어지는 결과를 초래한다.

 

그에 비해 카운팅 정렬 알고리즘의 시간 복잡도는 Θ(n) 이므로, 확실히 동작 시간 측면에서는 우수한 성능을 보인다.

 

* 그렇다면 무조건 카운팅 정렬을 사용하는 것이 좋을까? 그건 아니다.

예를 들어 {10, 17, 42, 20, 1500, 324} 와 같은 배열을 정렬할때 카운팅 정렬을 사용한다면 10~1500을 저장할 수 있는 배열이 필요하고 반복 횟수 또한 10~1500까지, 그러니까 1490번을 반복해야 할 것이다.

 

그러므로 이번 10989번 문제같은 제한적인 상황이 아니라면 선택 정렬을 사용하는 것이 여러모로 유리할 것이다.

 

 

 

문제점 2) Scanner를 BufferedReader로.

입력을 받기 위해 Scanner를 사용하면, 정규식 검사 과정에서 소요되는 시간이 비교적으로 크다.

따라서 BufferedReader를 사용하여 동작 시간을 단축시켰다.