문제 설명
당신은 카드 정리 전문가입니다. 각 카드에는 1부터 N까지의 숫자가 적혀있습니다.
그러나 카드들은 섞인 상태입니다. 당신의 목표는 주어진 카드들을 오름차순으로 정렬하는 것입니다.
당신은 각 카드를 한 번에 한 장씩 선택할 수 있습니다. 선택한 카드의 숫자를 기준으로
오름차순으로 정렬해야 합니다. 최소한의 비교 횟수로 카드를 정렬해야 합니다.
입력
첫째 줄에 카드의 개수 N(1 ≤ N ≤ 10^6)이 주어집니다.
둘째 줄에 N개의 정수 A1, A2, …, AN(1 ≤ Ai ≤ 10^9)이 주어집니다.
이 배열은 카드의 숫자를 나타냅니다.
출력
선출력에 각 카드의 숫자를 오름차순으로 정렬하여 한 줄에 출력합니다.
문제 해결 전략
카드 정렬 문제를 해결하기 위해서는 여러 가지 정렬 알고리즘을 사용할 수 있습니다.
특히, 퀵 정렬이나 병합 정렬과 같은 효율적인 정렬 알고리즘을 구현하면 좋습니다.
이 논의에서는 병합 정렬을 사용하여 문제를 해결하겠습니다.
병합 정렬(Merge Sort)
병합 정렬은 나누어 정복(Divide and Conquer) 알고리즘의 일종으로,
다음과 같은 단계를 거쳐 정렬합니다:
- 배열을 반으로 나눕니다.
- 각 반을 재귀적으로 정렬합니다.
- 정렬된 두 배열을 병합하여 최종적으로 정렬합니다.
자바 코드
public class CardSorting {
public static void main(String[] args) {
int[] cards = {3, 2, 5, 4, 1}; // 예제 입력
mergeSort(cards, 0, cards.length - 1);
System.out.println("정렬된 카드:");
for (int card : cards) {
System.out.print(card + " ");
}
}
public static void mergeSort(int[] array, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
merge(array, left, mid, right);
}
}
public static void merge(int[] array, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++) {
L[i] = array[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = array[mid + 1 + j];
}
int i = 0, j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
array[k] = L[i];
i++;
} else {
array[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
array[k] = L[i];
i++;
k++;
}
while (j < n2) {
array[k] = R[j];
j++;
k++;
}
}
}
복잡도 분석
병합 정렬의 시간 복잡도는
O(N log N)입니다. 이는 정렬된 두 개의 배열을 합치는 것이 O(N)이고, 배열을 계속 반으로 나누는 것이 log N에 해당하기 때문입니다.
따라서 대규모 카드 데이터에 대해서도 효율적으로 정렬할 수 있습니다.
마무리
이번 글에서는 카드 정렬 문제를 병합 정렬을 통해 해결해보았습니다.
자바를 사용한 병합 정렬의 구현을 통해 다양한 데이터 구조와 알고리즘의 중요성을 이해할 수 있습니다.
앞으로도 이러한 문제들을 지속적으로 다루어 자바 프로그래밍 실력을 가다듬어보시기 바랍니다.