개요
세 개의 정렬된 배열이 주어졌을 때, 이 배열들에 모두 존재하는 공통 요소를 효율적으로 찾는 방법을 알아보겠습니다. 예를 들어 다음과 같은 세 개의 배열이 있다고 가정해 보겠습니다.
- A1 = [10, 12, 15, 20, 25]
- A2 = [10, 12, 13, 15]
- A3 = [10, 12, 15, 24, 25, 26]
이 경우 세 배열의 공통 요소는 10, 12, 15입니다.
알고리즘 접근 방식
배열이 모두 정렬되어 있기 때문에, 각 배열에 포인터를 하나씩 두고 동시에 순회하는 투 포인터(Three Pointer) 기법을 사용할 수 있습니다. 배열 A1에서 현재 가리키는 요소를 x, A2를 y, A3를 z라고 할 때 다음 규칙에 따라 진행합니다.
- x = y = z인 경우: 세 값이 모두 같으므로 해당 값을 출력하고, 세 포인터를 모두 한 칸씩 앞으로 이동합니다.
- x < y인 경우: x보다 큰 y가 존재하므로 x는 공통 요소가 될 수 없습니다. A1의 포인터를 앞으로 이동합니다.
- y < z인 경우: 마찬가지로 y는 공통 요소가 될 수 없으므로 A2의 포인터를 앞으로 이동합니다.
- 그 외의 경우(z가 가장 작은 경우): z는 공통 요소가 될 수 없으므로 A3의 포인터를 앞으로 이동합니다.
이 방식은 각 배열을 한 번만 순회하므로 시간 복잡도는 O(n1 + n2 + n3)이며, 추가 메모리 사용 없이 제자리에서 해결할 수 있다는 장점이 있습니다.
C++ 구현 예제
#include<iostream>
using namespace std;
void findCommonValues(int A1[], int A2[], int A3[], int n1, int n2, int n3) {
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2 && k < n3) {
// 세 배열의 현재 요소가 모두 같으면 공통 요소
if (A1[i] == A2[j] && A2[j] == A3[k]) {
cout << A1[i] << " ";
i++; j++; k++;
}
else if (A1[i] < A2[j])
i++; // x가 가장 작으므로 A1 이동
else if (A2[j] < A3[k])
j++; // y가 가장 작으므로 A2 이동
else
k++; // z가 가장 작으므로 A3 이동
}
}
int main() {
int A1[] = {10, 12, 15, 20, 25};
int n1 = sizeof(A1)/sizeof(A1[0]);
int A2[] = {10, 12, 13, 15};
int n2 = sizeof(A2)/sizeof(A2[0]);
int A3[] = {10, 12, 15, 24, 25, 26};
int n3 = sizeof(A3)/sizeof(A3[0]);
cout << "Common elements are: ";
findCommonValues(A1, A2, A3, n1, n2, n3);
return 0;
}실행 결과
Common elements are: 10 12 15
마무리
세 개의 정렬된 배열에서 공통 요소를 찾는 문제는 투 포인터 기법을 활용하면 선형 시간 안에 해결할 수 있습니다. 핵심은 세 배열의 현재 값을 비교하여 가장 작은 값이 있는 배열의 포인터를 앞으로 이동시키는 것입니다. 이 접근 방식은 두 배열 이상의 교집합 문제로 확장하기도 쉬우므로, 코딩 인터뷰에서 자주 등장하는 유형이니 꼭 익혀두시기 바랍니다.