C++로 ab = cd를 만족하는 배열의 두 쌍 (a, b)와 (c, d) 찾는 방법

문제 개요

배열 A가 주어졌을 때, 이 배열에서 두 쌍 (a, b)와 (c, d)를 선택하여 곱이 서로 같아지도록 하는, 즉 ab = cd를 만족하는 모든 쌍을 찾는 문제입니다.

예를 들어 배열 A = [3, 4, 7, 1, 2, 9, 8]이 주어진다면 정답은 (4, 2)와 (1, 8)입니다. 두 쌍의 곱이 각각 4×2 = 8, 1×8 = 8로 동일하기 때문입니다.

접근 방법: 해시 테이블 활용

모든 네 원소 조합을 일일이 비교하는 브루트 포스 방식은 시간 복잡도가 O(n⁴)까지 늘어날 수 있어 비효율적입니다. 대신 가능한 모든 쌍의 곱을 계산하면서 해시 테이블에 저장하고, 같은 곱이 다시 등장하는 순간 기존 쌍과 새 쌍을 함께 출력하면 O(n²) 만에 문제를 해결할 수 있습니다.

알고리즘 단계

• i를 0부터 n-1까지 반복합니다.
• j를 i+1부터 n-1까지 반복합니다.
• 곱(product) = arr[i] × arr[j]를 계산합니다.
• 해시 테이블에 해당 곱이 없으면 Hash[product] = (i, j)로 저장합니다.
• 해시 테이블에 해당 곱이 이미 존재하면, 저장되어 있던 이전 쌍과 현재 쌍을 함께 출력합니다.

C++ 구현 예제

#include <iostream>
#include <unordered_map>
using namespace std;

void displayPairs(int arr[], int n) {
    bool found = false;
    unordered_map<int, pair<int, int>> Hash;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int prod = arr[i] * arr[j];
            if (Hash.find(prod) == Hash.end())
                Hash[prod] = make_pair(i, j);
            else {
                pair<int, int> pp = Hash[prod];
                cout << "(" << arr[pp.first] << ", " << arr[pp.second]
                      << ") and (" << arr[i] << ", " << arr[j] << ")" << endl;
                found = true;
            }
        }
    }
    if (!found)
        cout << "No pairs have Found" << endl;
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = sizeof(arr) / sizeof(int);
    displayPairs(arr, n);
}

실행 결과

(1, 6) and (2, 3)
(1, 8) and (2, 4)
(2, 6) and (3, 4)
(3, 8) and (4, 6)

출력 결과를 보면 각 줄의 두 쌍이 모두 같은 곱을 가집니다. 예를 들어 1×6 = 2×3 = 6, 1×8 = 2×4 = 8처럼 ab = cd 조건이 성립합니다.

복잡도 분석

• 시간 복잡도: O(n²) — 모든 쌍 (i, j)를 한 번씩 검사하며, 해시 테이블의 삽입과 탐색은 평균적으로 O(1)입니다.
• 공간 복잡도: O(n²) — 최악의 경우 모든 쌍의 곱이 서로 달라 해시 테이블에 쌍의 개수만큼 데이터가 저장될 수 있습니다.

정리

해시 테이블을 활용하면 곱이 같은 두 쌍을 찾는 문제를 브루트 포스보다 훨씬 효율적인 O(n²) 시간에 해결할 수 있습니다. 중복 없이 첫 번째로 발견된 쌍만 저장하기 때문에 출력되는 결과에는 중복 조합이 나타나지 않으며, 조건을 만족하는 쌍이 하나도 없을 경우 "No pairs have Found" 메시지로 안내됩니다.