[카테고리:] 자바 코딩테스트 강좌

문제 설명

주어진 수열을 정렬하는 문제는 알고리즘 문제 풀이에서 매우 흔하게 출제되는 유형입니다.
이번 문제는 “정렬하기 III”로, 정수 배열이 주어졌을 때, 이 배열을 오름차순으로 정렬하라는 문제입니다.
입력으로 주어진 배열의 크기 N (1 ≤ N ≤ 1,000,000)과 배열의 원소 A[i] (0 ≤ A[i] ≤ 1,000,000)가 주어집니다.
만약 A[i]가 이미 정렬된 형태일 경우, 추가적인 연산 없이 해당 배열을 그대로 출력하면 됩니다.

입력 형식

        첫 번째 줄에 정수 N이 주어진다.
        두 번째 줄에 N개의 정수 A[i]가 주어진다.
    

출력 형식

정렬된 정수 배열을 출력한다. 각 정수는 공백으로 구분된다.

문제 예시

        입력:
        5
        5 4 3 2 1

        출력:
        1 2 3 4 5
    

접근 방식

이 문제를 해결하기 위해서는 가장 먼저 입력받은 배열을 정렬해야 합니다.
자바에서는 Arrays.sort() 메서드를 이용해 손쉽게 정렬할 수 있지만,
정렬 알고리즘의 작동 원리를 이해하는 것도 중요합니다.
배워야 할 몇 가지 정렬 알고리즘으로는 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬 등이 있습니다.

여기서는 퀵 정렬을 사용하여 문제를 해결할 것입니다.
퀵 정렬은 평균적으로 O(N log N)의 시간 복잡도를 가지며,
일반적으로 많은 데이터 세트를 정렬하는데 가장 효율적인 방법 중 하나로 알려져 있습니다.

알고리즘 설명

1. 기본적으로 퀵 정렬은 피벗을 선택하고,
   피벗보다 작은 원소는 왼쪽에, 큰 원소는 오른쪽에 위치시키는 방식으로 동작합니다.
2. 배열을 분할하면서 정렬을 진행하며,
   기본적으로 재귀 호출을 통해 동작합니다.
3. 모든 원소가 정렬될 때까지 이 과정을 반복합니다.

코드 구현

        
            import java.util.Arrays;

            public class Main {
                public static void main(String[] args) {
                    Scanner scanner = new Scanner(System.in);
                    int n = scanner.nextInt();
                    int[] arr = new int[n];

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

                    // 배열 정렬
                    Arrays.sort(arr);

                    // 정렬된 배열 출력
                    for (int num : arr) {
                        System.out.print(num + " ");
                    }
                }
            }
        
    

최적화 방법

경우에 따라서 배열 요소의 범위가 작거나 특정 패턴이 있을 경우,
카운팅 정렬을 고려할 수도 있습니다.
카운팅 정렬은 O(N + K) 복잡도를 가지며, K는 배열 원소의 최댓값입니다.
원소의 분포가 좁다면 카운팅 정렬을 사용하여 성능을 극대화 할 수 있습니다.

예를 들어, 수의 범위가 0에서 1000으로 제한된다면,
0과 1000 사이의 값이 몇 번 등장하는지를 카운트하여 이를 기준으로 정렬할 수 있습니다.

카운팅 정렬 코드 구현

        
            import java.util.Scanner;

            public class CountingSort {
                public static void main(String[] args) {
                    Scanner scanner = new Scanner(System.in);
                    int n = scanner.nextInt();
                    int[] arr = new int[n];
                    int max = 1000000; // 문제의 조건으로 Max value

                    int[] count = new int[max + 1]; // Count array with size max + 1

                    // 입력받기
                    for (int i = 0; i < n; i++) {
                        arr[i] = scanner.nextInt();
                        count[arr[i]]++;
                    }

                    // 정렬하여 출력하기
                    for (int i = 0; i <= max; i++) {
                        while (count[i] > 0) {
                            System.out.print(i + " ");
                            count[i]--;
                        }
                    }
                }
            }
        
    

결론

이번 “정렬하기 3” 문제는 정렬 알고리즘의 기초적인 이해와 배열 처리를 연습할 수 있는 좋은 기회를 제공합니다.
퀵 정렬과 카운팅 정렬을 통해 정렬 알고리즘의 다양한 접근 방법을 배우는 것이 가능합니다.
앞으로 더 복잡한 문제를 해결하기 위해서는 이번 문제에서 배운 기초를 잘 이해하고 활용하는 것이 중요합니다.

추가 문제

이 문제를 바탕으로 변형된 문제를 생각해 보는 것도 좋은 연습이 될 것입니다.
예를 들어, 다음과 같은 문제를 만들어 보는 것도 좋습니다.

• 1에서 1000까지의 수를 무작위로 입력받은 뒤 각 숫자가 몇 번씩 등장하는지 구하는 문제
• 특정 간격으로만 정렬될 수 있는 수열을 정렬하는 문제
• 다른 정렬 알고리즘인 병합 정렬을 구현하는 문제