[백준] 2751 수 정렬하기 2 | 정렬 | 실버 Ⅴ | JAVA 💡계수 정렬

📌 문제

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

 

❌ 시간 초과 코드

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

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));
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(br.readLine());
        
        int[] a = new int[n];
        
        for (int i = 0; i<n; i++){
            a[i]=Integer.parseInt(br.readLine());
        }
        
        Arrays.sort(a);
        
        for (int i = 0; i<n; i++){
            sb.append(a[i]+"\n");
        }
        
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

🤔 시간 초과 이유

이 문제는 대부분 Arrays.sort 로 풀면 시간초과가 난다고 합니다!

그 이유는 Arrays.sort() 의 경우 dual-pivot Quicksort 알고리즘을 사용하여 평균 시간복잡도가 O(nlogn) 이고 매우 빠른 알고리즘이지만, 최악의 경우 시간복잡도는 O(n2)이 걸리기 때문입니다.

그래서 이 문제는 일부러 Arrays.sort()를 쓰지 못하게 O(n2) 이 걸리도록 저격한 데이터가 있다고 하네요..💦

그래서 처음에는 Collections.sort() 로 해결했습니다!

Collections.sort() 은 Timsort인데, Timsort 의 경우 합병 및 삽입정렬 알고리즘을 사용합니다.

합병 정렬의 경우 최선, 최악 모두 O(nlogn)을 보장하고, 삽입 정렬의 경우, 최선의 경우는 O(n) , 최악의 경우는 O(n2) 입니다.

아래 코드가 Collections.sort()로 해결한 코드입니다!

 

✅ Pre-Refactor Code

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

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));
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(br.readLine());
        
        // int[] a = new int[n];
        List<Integer> a = new ArrayList<>();
        
        for (int i = 0; i<n; i++){
            // a[i]=Integer.parseInt(br.readLine());
            a.add(Integer.parseInt(br.readLine()));
        }
        
        // Arrays.sort(a);
        Collections.sort(a);
        
        for (int i = 0; i<n; i++){
            sb.append(a.get(i)+"\n");
        }
        
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

문제는 풀었지만, 시간이 무려 1464ms가 나왔는데요..?

아무리 자바라고 해도 이건 너무한 거 같아서 다른 사람들의 코드를 참고했습니다!

첫인상은 굉장히 괴상했지만, 이해하고 나니 코드도 엄청 쉽고 시간복잡도도 무려 O(N)이라는 사실!

 

🔄️ Refactored Code

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

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));
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(br.readLine());
        
        // int[] a = new int[n];
        // List<Integer> a = new ArrayList<>();
        boolean[] a = new boolean[2000001];
        
        for (int i = 0; i<n; i++){
            // a[i]=Integer.parseInt(br.readLine());
            a[Integer.parseInt(br.readLine())+1000000] = true;
        }
        
        // Arrays.sort(a);
        // Collections.sort(a);
        
        for (int i = 0; i<a.length; i++){
            // sb.append(a.get(i)+"\n");
            if (a[i]){
                sb.append(i-1000000+"\n");
            }
        }
        
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

이 코드는 주어진 문제를 해결하기 위해 boolean 배열을 사용하여 입력된 숫자를 기록하고, 이를 통해 정렬된 결과를 출력하는 방식입니다.

각 부분을 단계별로 설명해드리겠습니다!

1️⃣ 문제 읽기

입력 : 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

절댓값이 1,000,000보다 작거나 같은 정수라고 주어졌으니, 입력된 숫자는 -1,000,000에서 1,000,000까지의 범위에 있다는 것을 알 수 있습니다!

2️⃣ boolean 배열 크기 

boolean[] a = new boolean[2000001];

여기서 a 배열의 크기를 2000001로 했는데요 이 이유는 -1,000,000에서 1,000,000까지의 모든 수를 표현하기 위함 입니다.

배열의 인덱스를 0부터 2000000까지 사용합니다. 여기서 0은 -1,000,000, 1은 -999,999, ..., 1000000은 0, 2000000은 1,000,000을 나타냅니다.

즉, i 번째 인덱스는 실제 숫자 i - 1000000을 의미합니다!

3️⃣ 입력 처리

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

N개의 숫자를 입력받아 각각의 숫자를 arr 배열의 해당 인덱스에 true로 설정합니다.

예를 들어, 입력으로 -999999가 들어오면 arr[1]을 true로 설정하게 됩니다.

4️⃣ 출력 처리

for (int i = 0; i < a.length; i++) {
    if (a[i]) {
        sb.append(i-1000000+"\n");
    }
}

arr 배열을 순회하면서 true인 인덱스를 찾습니다. 이 인덱스는 입력된 숫자를 의미하므로, i - 1000000을 통해 원래의 숫자로 변환합니다.

 

⭐ 결론

Arrays.sort 시간 초과, Collections.sort 1464ms, 계수 정렬 580ms

계수 정렬을 통해 가장 빠른 시간에 문제를 해결할 수 있었습니다!

입력된 모든 숫자를 기록하기 위해 boolean 배열을 사용하고, 각 인덱스를 통해 정렬된 결과를 출력합니다.

배열을 통해 직접적인 인덱스 접근으로 정렬된 결과를 쉽게 얻을 수 있어 매우 빠르게 처리할 수 있습니다.

이러한 방식 덕분에 시간 복잡도는 O(N)으로, 대량의 입력을 효과적으로 처리할 수 있습니다.