문제 이해하기
세 개의 정렬된 배열 A, B, C가 있다고 가정해 봅시다(각 배열의 크기는 서로 달라도 괜찮습니다). 각 배열에서 하나의 원소씩 선택해 만든 세 쌍 (A[i], B[j], C[k])에 대해, |max(A[i], B[j], C[k]) − min(A[i], B[j], C[k])|, 즉 최댓값과 최솟값의 차이가 가장 작아지는 경우를 찾아야 합니다.
예를 들어 입력이 다음과 같다고 해보겠습니다.
A = [2, 5, 6, 9, 11], B = [7, 10, 16], C = [3, 4, 7, 7]
이때 A[i] = 6, B[j] = 7, C[k] = 7을 선택하면 차이는 |7 − 6| = 1이 되며, 이것이 가능한 최솟값입니다. 따라서 출력은 1입니다.
접근 방법
세 배열이 모두 오름차순으로 정렬되어 있기 때문에, 투 포인터(two pointer)와 유사한 방식으로 각 배열의 끝에서부터 탐색하면 선형 시간 안에 문제를 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 현재 조합에서 가장 큰 값을 가진 배열의 인덱스를 하나 감소시킵니다. 정렬된 배열이므로 최댓값을 줄여야만 전체 차이가 줄어들 가능성이 있습니다.
- 매 단계마다 현재 차이를 계산하고, 기존 최솟값보다 작으면 갱신합니다.
- 어느 한 배열이라도 인덱스가 -1에 도달하면 탐색을 종료합니다.
알고리즘 단계
- i := len(A) − 1, j := len(B) − 1, k := len(C) − 1로 초기화합니다.
- minimum_difference := |max(A[i], B[j], C[k]) − min(A[i], B[j], C[k])|로 초기화합니다.
- i, j, k 중 하나라도 -1이 될 때까지 다음을 반복합니다.
- current_diff := |max(A[i], B[j], C[k]) − min(A[i], B[j], C[k])|를 계산합니다.
- current_diff < minimum_difference이면 minimum_difference를 current_diff로 갱신합니다.
- maximum_term := max(A[i], B[j], C[k])를 구합니다.
- A[i] == maximum_term이면 i를 1 감소시킵니다.
- B[j] == maximum_term이면 j를 1 감소시킵니다.
- 그 외의 경우에는 k를 1 감소시킵니다.
- 반복이 끝나면 minimum_difference를 반환합니다.
구현 예제
다음 파이썬 코드를 통해 동작 과정을 더 잘 이해할 수 있습니다.
def solve(A, B, C):
i = len(A) - 1
j = len(B) - 1
k = len(C) - 1
minimum_difference = abs(max(A[i], B[j], C[k]) - min(A[i], B[j], C[k]))
while i != -1 and j != -1 and k != -1:
current_diff = abs(max(A[i], B[j], C[k]) - min(A[i], B[j], C[k]))
if current_diff < minimum_difference:
minimum_difference = current_diff
maximum_term = max(A[i], B[j], C[k])
if A[i] == maximum_term:
i -= 1
elif B[j] == maximum_term:
j -= 1
else:
k -= 1
return minimum_difference
A = [2, 5, 6, 9, 11]
B = [7, 10, 16]
C = [3, 4, 7, 7]
print(solve(A, B, C))입력
A = [2, 5, 6, 9, 11] B = [7, 10, 16] C = [3, 4, 7, 7]
출력
1
복잡도 분석
시간 복잡도: 매 반복마다 세 인덱스 중 하나가 반드시 감소하므로, 전체 시간 복잡도는 O(n + m + p)입니다(n, m, p는 각 배열의 길이).
공간 복잡도: 추가적인 자료구조를 사용하지 않으므로 O(1)입니다.