서로 다른 양의 정수로 구성된 정렬된 배열이 있다고 가정해 보겠습니다. 이때 우리가 찾아야 할 것은 정수 공비(common ratio)를 가지며 등비수열을 형성하는 모든 삼중항(triplet)입니다.
예를 들어 배열이 [1, 2, 6, 10, 18, 54]라고 한다면, 답은 (2, 6, 18)과 (6, 18, 54)입니다. 각 삼중항은 공비 3을 가지는 등비수열을 이룹니다.
접근 방법
이 문제는 투 포인터(two pointer) 기법으로 효율적으로 해결할 수 있습니다. 배열의 두 번째 요소부터 시작하여 각 요소를 중간 요소로 고정한 뒤, 왼쪽에서는 더 작은 값을, 오른쪽에서는 더 큰 값을 탐색합니다.
중간 요소 arr[j]가 등비수열의 가운데 항이 되려면, 앞의 요소 arr[i]와 뒤의 요소 arr[k]는 다음 조건을 만족해야 합니다.
$$\frac{arr[j]}{arr[i]}=\frac{arr[k]}{arr[j]}=r$$
즉, 세 요소가 같은 비율 r로 증가해야 한다는 뜻입니다. 탐색 과정에서는 나눗셈 가능 여부(나머지 검사)와 몫의 크기를 비교하면서 포인터 i와 k를 적절히 이동시켜 모든 후보를 확인합니다.
예제 코드
#include<iostream>
using namespace std;
void getTriplets(int arr[], int n) {
for (int j = 1; j < n - 1; j++) {
int i = j - 1, k = j + 1;
while (i >= 0 && k <= n - 1) {
while (arr[j] % arr[i] == 0 && arr[k] % arr[j] == 0 && arr[j] / arr[i] == arr[k] / arr[j]) {
cout << "("<< arr[i] << ", " << arr[j] << ", " << arr[k] << ")" << endl;
k++;
i--;
}
if(arr[j] % arr[i] == 0 && arr[k] % arr[j] == 0) {
if(arr[j] / arr[i] < arr[k] / arr[j])
i--;
else
k++;
}else if (arr[j] % arr[i] == 0)
k++;
else
i--;
}
}
}
int main() {
int arr[] = {1, 2, 6, 10, 18, 54};
int n = sizeof(arr) / sizeof(arr[0]);
getTriplets(arr, n);
}실행 결과
(2, 6, 18) (6, 18, 54)
동작 원리 정리
- 배열이 정렬되어 있으므로, 중간 항 arr[j]를 기준으로 왼쪽 포인터 i는 감소하고 오른쪽 포인터 k는 증가하는 방향으로만 움직입니다.
- arr[j]가 arr[i]로 나누어떨어지고 arr[k]가 arr[j]로 나누어떨어지는 경우, 두 몫을 비교하여 어느 쪽 포인터를 이동할지 결정합니다.
- 나누어떨어지지 않는 경우에는 배수 관계가 성립하도록 해당 방향의 포인터를 이동시킵니다.
이 알고리즘의 시간 복잡도는 각 중간 요소에 대해 투 포인터 탐색을 수행하므로 O(n²)이며, 단순한 세 겹 반복문(O(n³))보다 효율적입니다. 또한 배열이 정렬되어 있고 요소가 서로 다르다는 전제 조건이 있기 때문에 포인터 이동 규칙을 단순하게 유지할 수 있습니다.