[백준] 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을 통해 원래의 숫자로 변환합니다.
⭐ 결론
계수 정렬을 통해 가장 빠른 시간에 문제를 해결할 수 있었습니다!
입력된 모든 숫자를 기록하기 위해 boolean 배열을 사용하고, 각 인덱스를 통해 정렬된 결과를 출력합니다.
배열을 통해 직접적인 인덱스 접근으로 정렬된 결과를 쉽게 얻을 수 있어 매우 빠르게 처리할 수 있습니다.
이러한 방식 덕분에 시간 복잡도는 O(N)으로, 대량의 입력을 효과적으로 처리할 수 있습니다.