문제 설명
주어진 수열을 정렬하는 문제는 알고리즘 문제 풀이에서 매우 흔하게 출제되는 유형입니다.
이번 문제는 “정렬하기 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)의 시간 복잡도를 가지며,
일반적으로 많은 데이터 세트를 정렬하는데 가장 효율적인 방법 중 하나로 알려져 있습니다.
알고리즘 설명
- 기본적으로 퀵 정렬은 피벗을 선택하고,
피벗보다 작은 원소는 왼쪽에, 큰 원소는 오른쪽에 위치시키는 방식으로 동작합니다. - 배열을 분할하면서 정렬을 진행하며,
기본적으로 재귀 호출을 통해 동작합니다. - 모든 원소가 정렬될 때까지 이 과정을 반복합니다.
코드 구현
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까지의 수를 무작위로 입력받은 뒤 각 숫자가 몇 번씩 등장하는지 구하는 문제
- 특정 간격으로만 정렬될 수 있는 수열을 정렬하는 문제
- 다른 정렬 알고리즘인 병합 정렬을 구현하는 문제