[백준] 수 정렬하기 3 JAVA

728x90

 

[백준] 수 정렬하기 3

---

접근

• 정렬

---

풀이

이 문제는 N개의 입력받는 수를 오름차순으로 정렬하여 출력하는 문제이다. 너무 간단하고 기본적인게 아닌가 했지만 시간 초과가 나는 것을 보고 그렇게 간단한 문제는 아니었구나 해서 문제를 가져왔다.

 

문제를 보자마자 드는 생각은 그냥 배열이나 리스트에 쭉 받고 정렬하고 그대로 다시 쭉 출력하면 끝 아닌가? 그렇게 간단하게 코드를 작성한 후 바로 시간 초과가 났고 N의 범위는 10,000,000으로 기본 내장된 Arrays.sort나 Collections.sort로는 감당할 수 없는 시간이 요구되었나 보다. 그렇게 찾아 보던 중 입력받는 값의 범위가 정해져 있는 이런 상황에서 사용할 수 있는 카운팅 정렬이라는 것을 발견했다. 카운팅 정렬이란 숫자의 개수를 세어 배열에 저장해 두는 것으로 예를 들어 입력이 1 1 1 4 5 6 7 8 1 이고 입력받는 숫자의 범위가 1 <= n <= 10이라고 할 때 new int[11]의 배열을 만들어 두고 입력받은 수를 순회하며 각 숫자들이 몇 번 나왔는지 세는 방법이다. 위의 경우 1이 4번 나왔으니 배열의 1번지 값은 4가 되어 나중에 각 번지의 값만큼 출력해 준다.

 

그렇게 된다면 O(N + K)의 복잡도로 N의 최댓값 10,000,000과 문제에선 10,000 이하의 자연수로 K는 10,000이 되고 총복잡도는 10,000,000 + 10,000로 10,010,000의 시간을 가지게 된다.  기본 라이브러리인 Arrays.sort의 경우 퀵 정렬이나 병합 정렬을 사용한다고 되어있는데 퀵 정렬의 시간 복잡도는 O(N log N)으로 최댓값인 10,000,000을 기준으로 계산했을 때 대략 2.3억이라는 값으로 카운팅 정렬에 비하면 대략 23배의 시간이 더 소요된다고 보면 된다. 또한 대용량으로 입력을 받아 Scanner대신 BufferedReader와 BufferedWriter를 사용해 속도를 높여 주었다. Scanner는 정규 표현식을 사용해 입력을 파싱 하는 과정이 존재해 많은 오버헤드가 발생하여 처리 속도가 느린 반면 BufferReader의 경우 파싱 과정이 없고 버퍼에 모아뒀다 처리하므로 대용량에선 성능 차이가 크게 발생한다.

 	int N = Integer.parseInt(br.readLine());
        int[] count = new int[10001];

    
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            count[num]++;
        }

카운팅 정렬을 위해 count 배열을 선언해 주고 입력받는 숫자들의 개수를 저장한다.

for (int num = 1; num <= 10000; num++) {
	while (count[num] > 0) {
		bw.write(num + "\n");
		count[num]--;
	}
}

1부터 저장한 숫자들의 개수만큼 출력을 해주게 되면 오름차순으로 정렬되어 출력되게 된다.

---

전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        int N = Integer.parseInt(br.readLine());
        int[] count = new int[10001]; 

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(br.readLine());
            count[num]++;
        }

        for (int num = 1; num <= 10000; num++) {
            while (count[num] > 0) {
                bw.write(num + "\n");
                count[num]--;
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

 

사실 이건 여담인데 굳이 카운팅 정렬을 사용하지 않아도 Scanner 대신 BufferedReader와 BufferedWriter만 사용해도 통과가 되긴 한다는 걸 알았다. 기본 Arrays.sort 퀵 정렬을 사용할 경우 2544ms  카운팅 정렬을 사용할 경우 1796ms로 대략 800ms 정도 빨라졌지만 제한 시간이었던 3초를 생각하면 아슬아슬했다.