BOJ_10989 : 수 정렬하기 3

👉 문제링크

10989번: 수 정렬하기 3

---

---

🔸 문제 분석 🔸

• 중복 가능한 n개의 수가 10,000,000개 이하로 입력되면 오름차순 정렬 후 출력한다.
  • O(n^2) 일때, 100,000,000,000,000(백 조) 이므로 제한시간 3초를 넘기게 된다.
  • 일반적인 Arrays.sort()는 평균 O(nlogn)이지만, 최악의 경우 O(n^2)이 나온다.
  • 이 문제는 입출력 속도를 빠르게 하면 아슬아슬하게 통과는 가능하다.
• 카운팅 정렬을 사용해야한다.
  • 입력되는 숫자를 인덱스로, 카운트를 진행하고 출력한다.

🔸 코드 🔸

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int arr[] = new int[10001];
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++){
            arr[Integer.parseInt(br.readLine())]++;
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 1; i < 10001; i++){
            while (arr[i] > 0){
                sb.append(i).append('\n');
                arr[i]--;
            }
        }
        System.out.println(sb);
    }
}

🔸 코드 해석 🔸

• 입력되는 n개의 숫자들의 범위가 1~10000이므로, 인덱스로 저장하기 위한 배열 arr를 선언한다.
  • 입력된 수를 인덱스로 배열 arr에 카운트한다.
• 배열 arr를 1부터 끝까지 순회하며 각 인덱스가 0이 될때까지, 해당 인덱스를 출력한다.
• 입력 속도를 높이기 위해 BufferedReader와 StringBuilder를 사용했다.

🔸 다른 풀이 🔸

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        int arr[] = new int[n];

        for (int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        for (int i = 0; i < n; i++){
            sb.append(arr[i]).append('\n');
        }
        System.out.println(sb);
    }
}

• 입력 된 수를 배열 arr에 순서대로 저장한 뒤 Arrays.sort()로 정렬한다.
  • Arrays.sort()는 dual-pivot Quick sort 알고리즘을 사용해 평균 시간 복잡도가 O(nlogn)이지만,
    최악의 경우 O(n^2)로 좋지 않은 성능이 나오기도 한다고 한다.

---

🔸 end 🔸

• 브론즈 1 문제였지만, 생각보다 어려운 문제였다고 생각한다.
• 정렬 시리즈의 끝판 문제인데, 카운팅 정렬을 제대로 이해할 수 있었던 것 같다.
  • 예전에 python으로 풀다가 포기한 문제였는데...답을 찾아보지 않으려고 고집 부렸던 것 같다.
• 이 문제에서 Arrays.sort()와 카운팅 정렬의 차이는 2배정도 나는 것 같다.