개념
크기가 서로 같지 않아도 되는 세 개의 정렬된 배열 A, B, C가 주어졌을 때, 각 배열에서 하나씩 선택한 세 원소 A[i], B[j], C[k]로 구성된 삼중항(triplet)에 대해 최댓값과 최솟값의 절대 차이가 가장 작아지도록 만들어야 합니다. 즉, 아래 식을 최소화하는 것이 목표입니다.
max(A[i], B[j], C[k]) − min(A[i], B[j], C[k])
입력 예시 1
A : [ 2, 5, 6, 9, 11 ]
B : [ 7, 10, 16 ]
C : [ 3, 4, 7, 7 ]
출력
1
설명
A[i] = 6, B[j] = 7, C[k] = 7을 선택하면 max(A[i], B[j], C[k]) − min(A[i], B[j], C[k]) = |7 − 6| = 1이 되어 최소 차이를 얻을 수 있습니다.
입력 예시 2
A = [ 6, 9, 11, 16 ]
B = [ 7, 10, 16, 79, 90 ]
C = [ 3, 4, 7, 7, 9, 9, 11 ]
출력
1
설명
A[i] = 11, B[j] = 10, C[k] = 11을 선택하면 max(A[i], B[j], C[k]) − min(A[i], B[j], C[k]) = |11 − 10| = 1이 되어 최소 차이를 얻을 수 있습니다.
접근 방법
먼저 세 배열 A, B, C에서 각각 가장 큰 원소(마지막 인덱스)부터 시작합니다. 그리고 매 단계마다 정답을 갱신할 수 있도록 별도의 변수를 유지합니다.
매 단계에서 차이를 줄일 수 있는 유일한 방법은 세 원소 중 최댓값을 줄이는 것입니다. 따라서 현재 최댓값을 포함하고 있는 배열의 바로 다음(더 작은) 원소로 이동한 뒤, 정답 변수를 갱신합니다.
최댓값을 포함한 배열이 끝날 때까지 이 과정을 반복하면 됩니다. 이 알고리즘은 세 개의 포인터를 사용하므로 시간 복잡도는 O(n1 + n2 + n3)이며, 여기서 n1, n2, n3는 각 배열의 길이입니다.
예제 코드(C++)
// 위 접근 방식에 대한 C++ 코드
#include<bits/stdc++.h>
using namespace std;
int solve(int A1[], int B1[], int C1[], int i1, int j1, int k1) {
int min_diff, current_diff, max_term;
// 리스트의 마지막 인덱스부터 최소 차이 계산
min_diff = abs(max(A1[i1], max(B1[j1], C1[k1]))
- min(A1[i1], min(B1[j1], C1[k1])));
while (i1 != -1 && j1 != -1 && k1 != -1) {
current_diff = abs(max(A1[i1], max(B1[j1], C1[k1]))
- min(A1[i1], min(B1[j1], C1[k1])));
// 조건 검사
if (current_diff < min_diff)
min_diff = current_diff;
// 리스트에서 최댓값 항 계산
max_term = max(A1[i1], max(B1[j1], C1[k1]));
if (A1[i1] == max_term)
i1 -= 1;
else if (B1[j1] == max_term)
j1 -= 1;
else
k1 -= 1;
}
return min_diff;
}
int main() {
int D1[] = { 5, 8, 10, 15 };
int E1[] = { 6, 9, 15, 78, 89 };
int F1[] = { 2, 3, 6, 6, 8, 8, 10 };
int nD = sizeof(D1) / sizeof(D1[0]);
int nE = sizeof(E1) / sizeof(E1[0]);
int nF = sizeof(F1) / sizeof(F1[0]);
cout << solve(D1, E1, F1, nD-1, nE-1, nF-1);
return 0;
}
출력
1