자바 코딩테스트 강좌, 수 정렬하기 2

이번 강좌에서는 자바를 이용한 코딩 테스트 준비를 위한 문제 “수 정렬하기 2”를 다룰 것입니다. 이 문제는 입력된 수를 오름차순으로 정렬하는 작업을 요구합니다. 특히, 효율적인 정렬 알고리즘을 구현하는 능력을 배양하는 것이 이번 강좌의 목표입니다. 문제를 해결하기 위한 과정과 함께, 자바 코드를 통해 해결 방법을 상세히 설명하겠습니다.

문제 정의

문제는 다음과 같이 주어집니다:


정수 N개가 주어질 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 
입력은 첫 줄에 정수 N(1 ≤ N ≤ 100,000)이 주어지고, 
다음 N줄에 걸쳐 입력되는 각 정수는 1,000,000보다 작거나 같은 자연수이다.

출력은 정렬된 순서대로 각 정수를 한 줄에 하나씩 출력해야 합니다.

예제 입력:
5
5
4
3
2
1

예제 출력:
1
2
3
4
5

문제 분석

주어진 문제는 기본적인 정렬 문제로, 다양한 정렬 알고리즘을 적용하여 풀 수 있습니다. 하지만, 입력의 크기(N)가 최대 100,000이고 각 수가 최대 1,000,000이므로, 효율적인 알고리즘이 필수입니다. 자바에서 사용할 수 있는 여러 정렬 알고리즘 중, 퀵 정렬(Quick Sort) 또는 머지 정렬(Merge Sort)와 같은 효율적인 O(N log N) 시간 복잡도를 가지는 알고리즘이 적합합니다.

알고리즘 선택

이번 강좌의 목표는 자바 코딩 테스트에 적합한 정렬 알고리즘을 구현하여 문제를 해결하는 것입니다. Java에서는 Arrays.sort() 메서드를 사용하여 정렬을 손쉽게 수행할 수 있지만, 이를 통해 정렬 알고리즘의 내부 동작 방식을 학습하는 것이 중요합니다. 그러므로 직접 정렬 알고리즘을 구현해보겠습니다.

퀵 정렬(Quick Sort) 알고리즘

퀵 정렬은 평균적인 시간 복잡도가 O(N log N)인 분할 정복 알고리즘입니다. 가장 먼저 피벗(pivot)을 선택한 후, 피벗보다 작은 값은 좌측에, 큰 값은 우측에 배치하여 분할합니다. 이후 재귀적으로 이 과정을 반복하여 정렬을 완성합니다. 전체적인 흐름은 다음과 같습니다:

배열에서 피벗을 선택합니다.
피벗을 기준으로 배열을 재배치합니다.
재배치된 배열을 기준으로 왼쪽과 오른쪽 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다.

자바 코드 구현

아래는 퀵 정렬 알고리즘을 사용하여 문제를 해결하는 자바 코드입니다:


import java.util.Scanner;

public class Main {
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            quickSort(array, low, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, high);
        }
    }

    public static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
                swap(array, i, j);
            }
        }
        swap(array, i + 1, high);
        return i + 1;
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] numbers = new int[N];

        for (int i = 0; i < N; i++) {
            numbers[i] = scanner.nextInt();
        }

        quickSort(numbers, 0, N - 1);

        for (int number : numbers) {
            System.out.println(number);
        }

        scanner.close();
    }
}

코드 설명

코드를 살펴보면, 먼저 입력을 통해 정수 N을 받고, subsequent 입력을 통해 정수들을 배열에 저장합니다. 그 후 quickSort 메서드를 호출하여 정렬을 수행하게 됩니다. partition 메서드는 피벗을 선택하고 배열을 분할하여 피벗의 최종 위치를 반환하며, swap 메서드는 배열 내 두 요소의 자리를 바꿉니다.

결론

이번 강좌를 통해 자바로 알고리즘 문제를 풀어보는 방법을 배웠습니다. “수 정렬하기 2” 문제는 기본적인 정렬 알고리즘을 이용하여 해결할 수 있는 문제였습니다. 실제로 퀵 정렬을 구현하여 정렬을 수행하는 과정을 통해, 알고리즘의 내부 작동 방식에 대한 이해를 높일 수 있었습니다. 이와 같은 문제를 통해 자바 코딩 테스트에서의 실력을 향상시키기를 바랍니다.