[BOJ #10989번] 수 정렬하기 3

[백준 온라인 저지] #10989번 (수 정렬하기 ) 문제풀이

문제만 보면 너무 쉽게 풀 수 있는 정렬문제이다. 하지만 여기서도 함정이 존재하게 되는데 그 함정에 대해서 한 번 살펴보자.

보기에는 쉬운 문제지만 입출력에 대해서 생각하지 않으면 풀 수 없는 문제이다.  

일반적으로 접근하는 방법은 Scanner를 이용해서 입력을 받을 뒤 System.out.print()를 이용해 출력하는 방법이다. 하지만 이렇게 접근하는 순간 시간초과라는 메세지를 얻게 될 것이다. (나는 분명 맞게 풀었는데??)

처음에는 입력된 모든 수를 int[] arr에 저장 한 뒤 Arrays.sort()를 이용해서 정렬한 뒤 배열을 출력하는 형태로 접근했다. 하지만 시간초과에 걸린 것을 보고 주어지는 수가 10000보다 작거나 같다는것을 이용해 계수 정렬을 이용해서 풀어보았지만 역시 시간초과에 걸리고 말았다.

* 시간초과에 걸리는 소스코드

Scanner in = new Scanner(System.in);
int testCase = in.nextInt();
int[] arr = new int[10001];
 
for (int i = 0; i < testCase; i++) {
    arr[in.nextInt()]++;
}
 
StringBuilder builder = new StringBuilder();
for (int i = 0; i < 10001; i++) {
    while (arr[i]-- > 0) {
        builder.append(i).append("\n");
    }
}
 
System.out.print(builder);

문제풀이의 접근은 Scanner와 BufferedReader의 차이점에 대해서 아는가?? 로 나눠질 수 있을 거 같다. 비록 내부의 정확한 구현은 모를지라도 데이터의 입력이 많다면 Scanner보다 BufferedReader를 사용하는게 더 효율적이라는 것만 인지해도 문제를 풀 수 있다.

* 시간초과에 걸리지 않는 소스코드

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testCase = Integer.parseInt(br.readLine());
int[] arr = new int[10001];
 
for (int i = 0; i < testCase; i++) {
    arr[Integer.parseInt(br.readLine())]++;
}
 
StringBuilder builder = new StringBuilder();
 
for (int i = 0; i < 10001; i++) {
    while (arr[i]-- > 0) {
        builder.append(i).append("\n");
    }
}
 
System.out.print(builder);

입력으로 BufferedReader를 사용한다면 계수 정렬과 Arrays.sort()모두 시간초과에 걸리지 않고 정답입니다!!를 얻어낼 수 있다.  

여기서 출력을 위해 StringBuilder를 이용하지 않고 BufferedWriter를 사용한다면 더 좋은 결과를 얻을 수 있다는 점도 생각해보면 좋을 것 같다.