연결 리스트(Linked List)로 표현된 여러 개의 원소와 목표 곱(product) K가 주어졌을 때, 리스트 안에서 서로 곱했을 때 K가 되는 두 숫자의 쌍(pair)이 존재하는지 확인하는 것이 이번 글의 과제입니다. 만약 조건을 만족하는 두 숫자가 있다면 해당 숫자들을 출력하고, 후보가 두 개 이상이라면 그중 아무거나 하나만 출력하면 됩니다.
예를 들어 연결 리스트가 {2, 4, 8, 12, 15}이고 K 값이 16이라면, 2 × 8 = 16이므로 결과는 (2, 8)이 됩니다.
접근 방법: 해싱(Hashing) 기법 활용
이 문제는 해시 테이블을 이용하면 효율적으로 해결할 수 있습니다. 알고리즘의 흐름은 다음과 같습니다.
먼저 해시 테이블(unordered_set)을 하나 준비합니다. 그다음 연결 리스트를 순차적으로 탐색하면서 각 노드의 데이터를 확인합니다. 현재 원소가 K를 나누어 떨어지게 하는지 검사하고, 나누어 떨어진다면 몫인 (K ÷ 현재 원소) 값이 이미 해시 테이블에 저장되어 있는지 확인합니다. 존재한다면 곱이 K가 되는 쌍을 찾은 것이므로 두 숫자를 출력하고 종료합니다. 쌍을 찾기 전까지는 현재 원소를 해시 테이블에 계속 삽입해 나갑니다.
이 방식은 한 번의 순회만으로 답을 찾을 수 있으며, 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)입니다.
C++ 구현 코드
#include <unordered_set>
#define MAX 100000
using namespace std;
class Node {
public:
int data;
Node* next;
};
void append(struct Node** start, int key) {
Node* new_node = new Node;
new_node->data = key;
new_node->next = (*start);
(*start) = new_node;
}
bool isPairPresent(Node* start, int K) {
unordered_set<int> s;
Node* p = start;
while (p != NULL) {
int current = p->data;
if ((K % current == 0) && (s.find(K / current) != s.end())) {
cout << current << " " << K / current;
return true;
}
s.insert(p->data);
p = p->next;
}
return false;
}
int main() {
Node* start = NULL;
int arr[] = {2, 4, 8, 12, 15};
int n = sizeof(arr)/sizeof(arr[0]);
for(int i = 0; i<n; i++){
append(&start, arr[i]);
}
if (isPairPresent(start, 16) == false)
cout << "NO PAIR EXIST";
}출력 결과
2 8
코드 동작 원리 정리
append 함수는 새 노드를 리스트 맨 앞에 추가하여 입력 배열의 원소들로 연결 리스트를 구성합니다. isPairPresent 함수가 핵심 로직을 담당하는데, 리스트를 처음부터 끝까지 한 번씩만 순회하면서 다음 두 조건을 동시에 검사합니다.
첫째, 현재 원소(current)가 K의 약수인지 확인합니다(K % current == 0). 둘째, K를 현재 원소로 나눈 몫(K / current)이 이전에 탐색한 원소들 중에 있는지 해시 테이블에서 조회합니다. 두 조건이 모두 충족되면 해당 쌍을 출력하고 true를 반환하며, 끝까지 탐색해도 쌍을 찾지 못하면 false를 반환해 main 함수에서 "NO PAIR EXIST" 메시지를 출력하게 됩니다.