세 개의 연결 리스트가 주어졌을 때, 이 세 리스트에 모두 존재하는 공통 원소를 찾는 문제를 생각해 봅시다. 예를 들어 리스트가 [10, 12, 15, 20, 25], [10, 12, 13, 15], [10, 12, 15, 24, 25, 26]라면, 세 리스트에 공통으로 포함된 원소는 10, 12, 15입니다.
이 문제는 해싱(Hashing) 기법을 활용하면 효율적으로 해결할 수 있습니다. 전체 풀이 과정은 다음과 같습니다.
알고리즘 접근 방식
빈 해시 테이블을 생성한 뒤, 첫 번째 리스트의 모든 원소를 순회하면서 해시 테이블에 삽입하고 각 원소의 빈도를 1로 표시합니다.
두 번째 연결 리스트를 순회하면서, 현재 원소가 해시 테이블에 존재하고 빈도가 1이라면 해당 값을 2로 갱신합니다.
세 번째 연결 리스트를 순회하면서, 현재 원소의 빈도가 2라면 해당 값을 3으로 갱신합니다.
마지막으로 해시 테이블을 다시 확인하여 빈도가 3인 원소, 즉 세 리스트 모두에 등장한 원소를 출력합니다.
이 방식은 각 리스트를 한 번씩만 순회하면 되므로, 시간 복잡도는 O(n₁ + n₂ + n₃)이며 공간 복잡도는 해시 테이블 크기에 비례해 O(n₁)입니다.
C++ 구현 예제
#include<iostream>
#include<cmath>
#include<unordered_map>
using namespace std;
class Node {
public:
int data;
Node* next;
};
void addNode(Node** start, int data) {
Node* newNode = new Node;
newNode->data = data;
newNode->next = (*start);
(*start) = newNode;
}
void findCommonValues(Node* list1, Node* list2, Node* list3) {
unordered_map<int, int> hash;
Node* p = list1;
while (p != NULL) {
hash[p->data] = 1;
p = p->next;
}
Node* q = list2;
while (q != NULL) {
if (hash.find(q->data) != hash.end()) hash[q->data] = 2;
q = q->next;
}
Node* r = list3;
while (r != NULL) {
if (hash.find(r->data) != hash.end() && hash[r->data] == 2)
hash[r->data] = 3;
r = r->next;
}
for (auto x : hash) {
if (x.second == 3)
cout << x.first << " ";
}
}
int main() {
Node* list1 = NULL;
addNode(&list1, 10);
addNode(&list1, 12);
addNode(&list1, 15);
addNode(&list1, 20);
addNode(&list1, 25);
Node* list2 = NULL;
addNode(&list2, 10);
addNode(&list2, 12);
addNode(&list2, 13);
addNode(&list2, 15);
Node* list3 = NULL;
addNode(&list3, 10);
addNode(&list3, 12);
addNode(&list3, 15);
addNode(&list3, 24);
addNode(&list3, 25);
addNode(&list3, 26);
cout << "Common elements are: ";
findCommonValues(list1, list2, list3);
}실행 결과
Common elements are: 10 12 15
코드 설명
addNode()함수는 리스트 맨 앞에 새 노드를 추가하는 역할을 합니다.findCommonValues()함수는unordered_map을 활용해 각 원소가 몇 개의 리스트에 등장했는지 빈도로 추적합니다.빈도 값이 1 → 2 → 3으로 단계적으로 갱신되므로, 최종적으로 값이 3인 원소만 정확히 세 리스트의 공통 원소가 됩니다.