C++로 행렬에서 곱이 K인 쌍이 존재하는지 확인하는 방법

문제 개요

N × M 크기의 행렬과 하나의 정수 K가 주어졌을 때, 행렬 안에서 서로 다른 두 원소의 곱이 K가 되는 쌍(pair)이 존재하는지 확인하는 것이 이번 글의 목표입니다.

예를 들어 다음과 같은 4 × 4 행렬이 있다고 가정해 보겠습니다.

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15	16

이때 K가 42라면, 6 × 7 = 42이므로 (6, 7)이라는 쌍이 행렬 안에 존재합니다.

풀이 접근: 해싱(Hashing) 활용

이 문제는 해시 테이블을 이용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

행렬의 모든 원소를 저장할 빈 해시 테이블(unordered_set)을 준비합니다.
행렬을 순회하면서 각 원소 matrix[i][j]에 대해 다음 조건을 검사합니다.
① K가 현재 원소로 나누어 떨어지는지 (K % matrix[i][j] == 0)
② K를 현재 원소로 나눈 몫(K / matrix[i][j])이 이미 해시 테이블에 존재하는지
두 조건을 모두 만족하면 해당 쌍이 존재하므로 true를 반환합니다.
조건을 만족하지 않으면 현재 원소를 해시 테이블에 삽입하고 다음 원소로 넘어갑니다.
모든 원소를 순회한 후에도 쌍을 찾지 못했다면 false를 반환합니다.

이 방식은 각 원소마다 해시 테이블 조회가 O(1)에 이루어지므로, 전체 시간 복잡도는 O(N × M)이며 공간 복잡도 역시 O(N × M)입니다.

C++ 구현 예제

#include <iostream>
#include <unordered_set>
#define N 4
#define M 4
using namespace std;

bool isPairPresent(int matrix[N][M], int K) {
    unordered_set<int> s;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if ((K % matrix[i][j] == 0) && (s.find(K / matrix[i][j]) != s.end())) {
                return true;
            } else {
                s.insert(matrix[i][j]);
            }
        }
    }
    return false;
}

int main() {
    int matrix[N][M] = {{1, 2, 3, 4},
                        {5, 6, 7, 8},
                        {9, 10, 11, 12},
                        {13, 14, 15, 16}};
    int k = 42;
    if (isPairPresent(matrix, k) == false)
        cout << "NO PAIR EXIST";
    else
        cout << "Pair is present";
}

실행 결과

Pair is present

마무리

위 코드에서 K = 42를 넣으면 행렬의 원소 6을 처리하는 시점에, 앞서 해시 테이블에 저장된 7과의 곱이 42가 되므로 "Pair is present"가 출력됩니다. 반면 쌍이 존재하지 않는 K 값을 입력하면 "NO PAIR EXIST"가 출력됩니다. 이처럼 해싱을 활용하면 이중 반복문으로 모든 쌍을 직접 비교하는 O((N × M)²) 완전 탐색보다 훨씬 효율적으로 문제를 해결할 수 있습니다.