[백준 10989번] 수 정렬하기 3

문제 링크: 10989번 수 정렬하기 3

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

 

단순히 counting sort를 쓴다고 해서 통과하는 문제는 아니고,

알고리즘 문제를 풀 때 한 번쯤 거쳐가는, '불편하지만 빠른' 입출력 방식을 사용해야 하는 문제다.

 

자바의 경우, 입력에 대해서 다음과 같은 설명을 할 수 있다.

 

Scanner versus. BufferedReader

일반적으로는 Scanner 클래스를 이용하는데,

버퍼 크기가 1KB로 작고,

regExp를 통해 구문 분석 및 지정된 타입으로의 파싱을 진행하며,

동기화되어 있지 않아 멀티쓰레딩 환경에서 안전하지 않으며,

개발자가 Exception Handling을 진행하지 않는다.

 

반면 BufferedReader의 경우,

버퍼 크기가 8KB로 크고,

String만 읽으며,

동기화되어 있어 멀티쓰레딩 환경에서도 안전하며,

개발자가 Exception Handling을 진행한다.

 

아이러니하게도, BufferedReader가 synchronous함에도 불구하고,

버퍼 크기가 보다 크고 정규표현식을 사용하지 않는 이유 덕분에 훨씬 빠른 입력 속도를 보여준다.

 

출력에서도 그렇다.

StringBuilder를 통해서 문자열을 만들어 출력하는 것이, 일일이 System.out.print()를 통해 매번 write해주는 것보다 빠르다.

또는 입력에서처럼, BufferedWriter를 사용해도 좋다. 이 때에는 flush()를 잊으면 안 된다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        /* input */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        int m = -1; // arr의 원소 중 최댓값
        for (int i = 0; i < n; i++) {
            int cur = Integer.parseInt(br.readLine());
            arr[i] = cur;
            m = Math.max(m, cur);
        }

        /* counting sort */
        // create c of countingArr
        int[] c = new int[m+1];
        for (int i = 0; i < m+1; i++) {
            c[i] = 0;
        }

        // fill c
        for (int i = 0; i < n; i++) {
            c[arr[i]]++;
        }

        // update c to indexArr
        for (int i = 1; i < m+1; i++) {
            c[i] += c[i-1];
        }

        // create resultArr
        int[] r = new int[n];
        for (int i = 0; i < n; i++) {
            int idxForCurVal = --(c[arr[i]]);
            r[idxForCurVal] = arr[i];
        }

        /* print resultArr */
        for (int i = 0; i < n; i++) {
            sb.append(r[i]).append('\n');
        }

        System.out.println(sb);
    }
}