🧩 Baekjoon 2751 - 수 정렬하기 2

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제

✅ 입력 1

5
5
4
3
2
1

✅ 출력 1

1
2
3
4
5

작성 코드 1

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
  
public class Main {  
    public static void main(String[] args) throws IOException {  
        // 1. 변수 선언 및 초기화  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringBuilder sb = new StringBuilder();  
        int n = Integer.parseInt(br.readLine());  
        int[] arr = new int[n];  
        
        // 2. 배열 초기화  
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(br.readLine());  
        
        // 3. 퀵소트  
        quickSort(arr, 0, n - 1);  
        
        // 4. 출력  
        for (int i : arr) sb.append(i).append("\n");  
        sb.setLength(sb.length() - 1);  
        System.out.println(sb);  
    }  
    
    private static void quickSort(int[] arr, int left, int right) {  
        if (left >= right) return;  
        
        int index = partition(arr, left, right);  
        quickSort(arr, left, index - 1);  
        quickSort(arr, index, right);  
    }  
    
    private static int partition(int[] arr, int left, int right) {  
        int pivot = arr[(left + right) / 2];  
        
        while (left <= right) {  
            while (arr[left] < pivot) left++;  
            while (arr[right] > pivot) right--;  
            
            if (left <= right) {  
                swap(arr, left, right);  
                left++;  
                right--;  
            }  
        }  
        
        return left;  
    }  
    
    private static void swap(int[] arr, int i, int j) {  
        int temp = arr[i];  
        arr[i] = arr[j];  
        arr[j] = temp;  
    }  
}

• 최대 1_000_000 개의 수가 주어질 수 있다고 해서, 처음에는 무난하게 효율적인 퀵 정렬을 써보자고 생각했고, 시간 초과로 실패했다.

작성 코드 2

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 {
        // 1. 변수 선언 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        
        // 2. 배열 초기화
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(br.readLine());
        
        // 3. 정렬
        Arrays.sort(arr);
        
        // 4. 출력
        for (int i : arr) sb.append(i).append("\n");
        sb.setLength(sb.length() - 1);
        System.out.println(sb);
    }
}

• 일반 정렬로 바꾸니 성공은 했는데, TimSort, Dual-Pivot Quicksort를 사용하는 등 최적화가 되어 있어서 통과한 것 같다.
• 사실 계수 정렬을 생각해서 통과할지 몰랐는데, 이 부분은 나중에 조금 더 조사해봐야 한다.

작성 코드 3

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
  
public class Main {  
    private static final int OFFSET = 1_000_000;  
    private static final int MAX_VALUE = 2_000_000;  
    public static void main(String[] args) throws IOException {  
        // 1. 변수 선언 및 초기화  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringBuilder sb = new StringBuilder();  
        int[] arr = new int[MAX_VALUE + 1];  
        int n = Integer.parseInt(br.readLine());  
        
        // 2. 배열 초기화  
        for (int i = 0; i < n; i++) arr[Integer.parseInt(br.readLine()) + OFFSET] = 1;  
        
        // 3. 출력  
        for (int i = 0; i <= MAX_VALUE; i++) {  
            if (arr[i] == 1) sb.append(i - OFFSET).append("\n");  
        }  
        
        System.out.println(sb);  
    }  
}

• 계수 정렬로 구현했다.
• 확실히 더 효율적이긴 한데 음수도 따로 처리해줘야 하고, 실제로 쓸 수 있는 사례가 있을지 궁금하다.
• 다음은 java.util.Arrays에서 제공하는 sort()와 계수 정렬 알고리즘의 성능을 비교한 표다.

알고리즘	메모리	시간
sort()	109472	1548
계수 정렬	99952	680