문제 정의
세 개의 정렬된 배열 A, B, C가 있다고 가정해 봅시다. 각 배열에서 하나씩 요소를 선택했을 때, max(|A[i] – B[j]|, |B[j] – C[k]|, |C[k] – A[i]|) 값이 최소가 되도록 하는 조합을 찾는 것이 목표입니다.
예를 들어 A = [1, 4, 10], B = [2, 15, 20], C = [10, 12]라고 하면, 출력 결과는 10, 15, 10입니다. 이 세 값은 각각 배열 A, B, C에서 가져온 요소입니다.
접근 방법
배열 A, B, C의 크기를 각각 p, q, r이라고 합시다. 세 배열이 모두 정렬되어 있으므로, 세 개의 포인터를 활용하면 O(p + q + r) 시간 복잡도로 효율적으로 해결할 수 있습니다. 참고로 세 값 중 최댓값과 최솟값의 차이가 곧 세 쌍의 차이 중 최댓값과 같습니다. 해결 절차는 다음과 같습니다.
- i := 0, j := 0, k := 0으로 초기화합니다.
- i < p, j < q, k < r을 만족하는 동안 아래 과정을 반복합니다.
- A[i], B[j], C[k] 중에서 최솟값과 최댓값을 구합니다.
- diff := max(A[i], B[j], C[k]) − min(A[i], B[j], C[k])를 계산합니다.
- 계산한 diff가 지금까지의 결과보다 작으면 결과를 새 값으로 갱신합니다.
- 최솟값을 포함하는 배열의 포인터를 하나 증가시킵니다. 배열이 오름차순으로 정렬되어 있으므로, 가장 작은 값을 키워야만 전체 차이를 줄일 수 있기 때문입니다.
구현 예제
#include <iostream>
using namespace std;
void getClosestElements(int A[], int B[], int C[], int p, int q, int r) {
int diff = INT_MAX;
int i_final = 0, j_final = 0, k_final = 0;
int i = 0, j = 0, k = 0;
while (i < p && j < q && k < r) {
int min_element = min(A[i], min(B[j], C[k]));
int max_element = max(A[i], max(B[j], C[k]));
if (max_element - min_element < diff) {
i_final = i, j_final = j, k_final = k;
diff = max_element - min_element;
}
if (diff == 0)
break;
if (A[i] == min_element)
i++;
else if (B[j] == min_element)
j++;
else
k++;
}
cout << A[i_final] << " " << B[j_final] << " " << C[k_final];
}
int main() {
int A[] = {1, 4, 10};
int B[] = {2, 15, 20};
int C[] = {10, 12};
int p = sizeof A / sizeof A[0];
int q = sizeof B / sizeof B[0];
int r = sizeof C / sizeof C[0];
cout << "Closest elements are: ";
getClosestElements(A, B, C, p, q, r);
}실행 결과
Closest elements are: 10 15 10
복잡도 분석
매 반복마다 세 포인터 중 하나는 반드시 앞으로 이동하므로, 전체 반복 횟수는 최대 p + q + r번입니다. 따라서 시간 복잡도는 O(p + q + r)이며, 추가적인 저장 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다. 또한 diff가 0이 되면 더 이상 개선할 여지가 없으므로 즉시 반복을 종료하여 불필요한 연산을 줄일 수 있습니다.