[java] 중간 값 찾기 알고리즘의 최적화 방법
중간 값 찾기는 배열 또는 리스트에서 중간에 위치한 값을 찾는 알고리즘입니다. 이 알고리즘은 여러 가지 방법으로 구현할 수 있으며, 이번 글에서는 중간 값 찾기 알고리즘의 최적화 방법에 대해 알아보겠습니다.
1. 방법 1: 정렬 후 중간 값 찾기
가장 간단한 방법은 배열을 정렬한 다음, 중간에 위치한 값을 반환하는 것입니다. 이 방법은 배열을 정렬하는 시간이 필요하기 때문에 시간 복잡도가 O(n log n)이 됩니다.
import java.util.Arrays;
public class FindMedian {
public static int findMedian(int[] arr) {
Arrays.sort(arr);
int mid = arr.length / 2;
return arr[mid];
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 7};
int median = findMedian(arr);
System.out.println("Median: " + median);
}
}
2. 방법 2: QuickSelect 알고리즘
QuickSelect 알고리즘은 정렬을 하지 않고 중간 값을 찾는 효율적인 방법입니다. QuickSort 알고리즘에서 파생된 알고리즘이며, 평균 시간 복잡도가 O(n)입니다.
public class FindMedian {
public static int findMedian(int[] arr, int left, int right) {
if (left == right) {
return arr[left];
}
int pivotIndex = partition(arr, left, right);
int mid = arr.length / 2;
if (mid == pivotIndex) {
return arr[mid];
} else if (mid < pivotIndex) {
return findMedian(arr, left, pivotIndex - 1);
} else {
return findMedian(arr, pivotIndex + 1, right);
}
}
public static int partition(int[] arr, int left, int right) {
int pivotValue = arr[right];
int pivotIndex = left;
for (int i = left; i < right; i++) {
if (arr[i] <= pivotValue) {
swap(arr, i, pivotIndex);
pivotIndex++;
}
}
swap(arr, pivotIndex, right);
return pivotIndex;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 7};
int median = findMedian(arr, 0, arr.length - 1);
System.out.println("Median: " + median);
}
}
3. 결론
중간 값 찾기 알고리즘은 간단한 문제이지만, 효율적인 처리를 위해 최적화된 방법을 사용해야 합니다. 정렬 후 중간 값 찾기와 QuickSelect 알고리즘은 각각의 장단점이 있으며, 상황에 따라 적절한 방법을 선택해야 합니다.
더 자세한 내용은 아래 참고 자료를 참고하세요.