백준 10989번 수 정렬하기 3

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

10989번: 수 정렬하기 3

분류 : 정렬

 

 

게임에서 브론즈 실버라는 등급은 무시받기 쉬운 계급입니다.

solved.ac에서 정한 백준 문제의 티어가 브론즈 실버라면 

 

이 정도쯤이야..ㅋ

 

많이 얕잡아보는 경향이 있습니다.

실버 5 티어의 문제라 할지라도 시간제한과 메모리 제한을 신경 쓰지 않는다면..

원트라이로 문제를 풀 순 없겠죠.

이 문제의 정답률이 23%인 것만 봐도 많은 사람들이 어딘가에서 걸려 넘어졌네요.

 

저도 그랬습니다.

 

 

java

import java.io.*;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int[] arr = new int[num];
        for(int i = 0; i < num; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);
        for(int j = 0; j < num; j++){
            bw.write(String.valueOf(arr[j])+"\n");
        }
        bw.flush();
        bw.close();
    }
}

"시간 초과"

 

자바로 알고리즘 문제를 풀 때 Scanner보다 BufferedReader를 선호하는 편입니다.

이 둘의 차이점은 나중 게시글로 자세히 알아보겠지만 

간단하게 정리해보면,

1. BufferedReader는 동기화되지만 Scanner는 동기화되지 않습니다.
2. BufferedReader의 버퍼 크기는 8kb로 Scanner의 버퍼 크기 1kb보다 큽니다.
3. BufferedReader는 데이터를 그대로 받지만 Scanner는 문자열 파싱을 합니다.

등등의 이유로 BufferedReader의 속도가 Scanner보다 빠릅니다.

 

... 라고 우리의 선생님 stack overflow께서 알려주셨는데요.

다른 블로그도 똑같네요.. 이 부분은 제 나름대로 깔끔하게 정리해보긴 해야겠습니다.

비슷한 이유로 println문을 사용하는 것보다는 BufferedWriter를 선호합니다.

여기까진 괜찮습니다. 시간 초과는 이 부분에서 걸리지 않았습니다.

 

문제가 되는 코드는 Arrays 클래스의 sort() 메소드에서 걸렸습니다.

데이터가 너무 커서 최악의 시간 복잡도 O(n²)를 가지나 봅니다.

 

 

 

이럴 땐 Counting Sort (계수 정렬) 알고리즘을 사용합니다.

Counting Sort 알고리즘은 시간 복잡도 O(n)을 갖습니다.

10989번 문제처럼 수의 범위가 정해져 있을 때 유용한 알고리즘입니다.

배열을 미리 만들어놓고, 데이터와 똑같은 값의 인덱스에 그 개수를 저장하는 것이죠.

특정 조건에서 매우 빠른 알고리즘이지만 그만큼 단점도 존재합니다.

데이터 내 숫자의 최댓값이 클수록 배열도 길어지고

그만큼 사용하지 않는 불필요한 메모리가 생기겠죠?

 

수정한 코드는 아래와 같습니다.

 

java

import java.io.*;
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int[] arr = new int[10001];
        for(int i = 0; i < num; i++){
            arr[Integer.parseInt(br.readLine())]++;
        }
        for(int j = 0; j < 10001; j++){
            if(arr[j]>0) {
                for(int k = 0; k < arr[j]; k++) {
                    bw.write(String.valueOf(j + "\n"));
                }
            }
        }
        bw.flush();
        bw.close();
    }
}