이번 강좌에서는 자바에서 흔히 출제되는 알고리즘 문제 중 하나인 “배열에서 K번째 수 찾기” 문제를 다루어 보겠습니다. 이 문제는 주어진 배열에서 K번째로 작은 수를 찾는 것이며, 다양한 방법으로 접근할 수 있습니다. 이러한 유형의 문제를 해결하는 능력은 취업 코딩 테스트에서 매우 중요하므로, 이를 통해 코딩 실력을 한 단계 업그레이드할 수 있도록 합시다.
문제 정의
주어진 배열의 수에서 K번째로 작은 수를 찾아 반환하는 함수를 작성하시오. 입력: - 정수 배열 arr: n (1 ≤ n ≤ 1000) 크기의 배열 - 정수 K: K는 1 이상 n 이하의 값 출력: - 배열에서 K번째로 작은 수를 반환
예시
예를 들어, arr = [7, 10, 4, 3, 20, 15]이고 K = 3이라면, 답은 7이 됩니다.
접근 방법
이 문제를 해결하기 위해 여러 가지 방법을 고려할 수 있습니다. 가장 기본적인 접근은 다음과 같습니다.
- 정렬을 이용한 방법: 배열을 정렬한 후 K-1 번째 인덱스의 값을 반환합니다.
- 선택 알고리즘(Quickselect): Quickselect 알고리즘을 사용하여 K번째 수를 직접 찾을 수 있습니다.
- 힙을 이용한 방법: 최소 힙(min-heap)을 이용하여 K번째 최소값을 구할 수 있습니다.
방법 1: 정렬을 이용한 방법
가장 직관적인 방법은 배열을 정렬한 후 K-1 번째 인덱스의 값을 반환하는 것입니다. 정렬 알고리즘 중 하나를 사용하여 배열을 정렬하면 시간 복잡도는 O(n log n)입니다.
public class KthSmallestNumber {
public static int findKthSmallest(int[] arr, int K) {
Arrays.sort(arr);
return arr[K - 1];
}
public static void main(String[] args) {
int[] arr = {7, 10, 4, 3, 20, 15};
int K = 3;
System.out.println("K번째 작은 수: " + findKthSmallest(arr, K)); // 7
}
}
방법 2: Quickselect 알고리즘
Quickselect 알고리즘은 빠른 정렬(Quicksort)와 유사한 과정을 통해 K번째 smallest element를 빠르게 찾는 방법입니다. 이 알고리즘은 평균적으로 O(n)의 성능을 가집니다.
Quickselect는 피벗을 선택하고, 피벗을 기준으로 작은 값과 큰 값으로 분할합니다. 이후 K번째 수가 위치할 부분을 재귀적으로 탐색합니다.
public class KthSmallestNumber {
public static int partition(int[] arr, int left, int right, int pivotIndex) {
int pivotValue = arr[pivotIndex];
swap(arr, pivotIndex, right); // 피벗을 배열의 가장 끝으로 이동
int storeIndex = left;
for (int i = left; i < right; i++) {
if (arr[i] < pivotValue) {
swap(arr, storeIndex, i);
storeIndex++;
}
}
swap(arr, storeIndex, right); // 피벗을 제자리로 이동
return storeIndex; // 피벗의 최종 인덱스를 반환
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static int quickSelect(int[] arr, int left, int right, int K) {
if (left == right) {
return arr[left]; // 배열에 한 개의 원소만 남았을 때
}
int pivotIndex = left + (right - left) / 2;
pivotIndex = partition(arr, left, right, pivotIndex);
if (K == pivotIndex) {
return arr[K];
} else if (K < pivotIndex) {
return quickSelect(arr, left, pivotIndex - 1, K);
} else {
return quickSelect(arr, pivotIndex + 1, right, K);
}
}
public static int findKthSmallest(int[] arr, int K) {
return quickSelect(arr, 0, arr.length - 1, K - 1);
}
public static void main(String[] args) {
int[] arr = {7, 10, 4, 3, 20, 15};
int K = 3;
System.out.println("K번째 작은 수: " + findKthSmallest(arr, K)); // 7
}
}
방법 3: 최소 힙을 이용한 방법
최소 힙(min-heap)은 항상 가장 작은 값이 루트에 위치하는 특성을 가지고 있습니다. 주어진 배열의 크기가 n일 때, 최소 힙으로 최소 K개의 원소를 추출하여 K번째 원소를 찾을 수 있습니다. 이 방법은 O(n + k log n)의 성능을 보입니다.
import java.util.PriorityQueue;
public class KthSmallestNumber {
public static int findKthSmallest(int[] arr, int K) {
PriorityQueue minHeap = new PriorityQueue<>();
for (int num : arr) {
minHeap.offer(num);
}
int kthSmallest = -1;
for (int i = 0; i < K; i++) {
kthSmallest = minHeap.poll();
}
return kthSmallest;
}
public static void main(String[] args) {
int[] arr = {7, 10, 4, 3, 20, 15};
int K = 3;
System.out.println("K번째 작은 수: " + findKthSmallest(arr, K)); // 7
}
}
결론
이번 강좌에서는 “배열에서 K번째 수 찾기”라는 문제를 통해 다양한 알고리즘 접근 방법을 살펴보았습니다. 정렬을 이용한 간단한 방법, Quickselect 알고리즘을 이용한 효율적인 방법, 그리고 최소 힙을 이용한 방법 세 가지를 소개했습니다. 알고리즘 문제 해결 능력을 기르기 위해서는 다양한 문제를 경험하고, 각각의 방법이 어떤 상황에서 최적의 성능을 보이는지에 대한 이해가 필요합니다.
이러한 문제들을 꾸준히 풀어보면서 자신만의 문제 해결 패턴과 전략을 구축해 나간다면, 코딩 테스트에서 좋은 결과를 얻을 수 있을 것입니다.
더 많은 알고리즘 문제와 그 해결책을 다루는 강좌를 통해 여러분의 코딩 실력이 한층 더 발전하기를 바랍니다.