문제 개요
두 개의 단일 연결 리스트(singly linked list)가 주어졌을 때, 두 리스트에 공통으로 존재하는 노드의 총 개수를 구하는 것이 목표입니다. 예를 들어, 첫 번째 리스트가 [15, 16, 10, 9, 7, 17]이고 두 번째 리스트가 [15, 16, 40, 6, 9]라면, 값이 15, 16, 9인 노드가 양쪽 모두에 존재하므로 공통 노드는 총 3개입니다.
접근 방법
두 개의 중첩 반복문(nested loop)을 사용하여 이 문제를 해결할 수 있습니다.
- 첫 번째 리스트를 처음부터 끝까지 순회하면서 각 노드를 하나씩 선택합니다.
- 선택한 노드의 데이터 값이 두 번째 리스트의 어떤 노드와 일치하는지 확인합니다.
- 일치하는 노드를 찾으면 카운터를 1 증가시키고 내부 반복문을 종료하여 같은 노드가 중복해서 계산되지 않도록 합니다.
- 외부 반복문이 끝날 때마다 두 번째 리스트 탐색 위치를 다시 처음으로 되돌립니다.
- 모든 순회가 완료되면 최종 카운트를 반환합니다.
이 알고리즘의 시간 복잡도는 O(m×n)(m, n은 각 리스트의 길이)이며, 별도의 추가 저장 공간이 필요 없어 공간 복잡도는 O(1)입니다.
예제 코드
#include<iostream>
using namespace std;
class Node {
public:
int data;
Node *next;
};
void prepend(Node** start, int new_data) {
Node* new_node = new Node;
new_node->data = new_data;
new_node->next = NULL;
if ((*start) != NULL){
new_node->next = (*start);
*start = new_node;
}
(*start) = new_node;
}
int countCommonNodes(Node** start1, Node** start2) {
Node* ptr = *start1;
Node* ptr1 = *start2;
int count = 0;
while (ptr != NULL) {
while (ptr1 != NULL) {
if (ptr->data == ptr1->data) {
count++;
break;
}
ptr1 = ptr1->next;
}
ptr1 = *start2;
ptr = ptr->next;
}
return count;
}
int main() {
Node* first = NULL;
Node* second = NULL;
prepend(&first, 15);
prepend(&first, 16);
prepend(&first, 10);
prepend(&first, 9);
prepend(&first, 7);
prepend(&first, 17);
prepend(&second, 15);
prepend(&second, 16);
prepend(&second, 40);
prepend(&second, 6);
prepend(&second, 9);
cout << "Number of common nodes:" << countCommonNodes(&first, &second);
}실행 결과
Number of common nodes:3
코드 설명
prepend() 함수는 리스트의 맨 앞에 새 노드를 삽입하는 역할을 합니다. 따라서 입력 순서와 달리 리스트는 역순으로 구성되지만, 공통 노드의 개수를 구하는 데에는 영향을 주지 않습니다.
실제 계산은 countCommonNodes() 함수에서 수행됩니다. 외부 반복문은 첫 번째 리스트를 순회하고, 내부 반복문은 해당 노드와 두 번째 리스트의 모든 노드를 비교합니다. 값이 일치하면 count를 증가시킨 뒤 break로 내부 반복문을 빠져나와 중복 집계를 방지합니다. 위 예제에서는 15, 16, 9 세 개의 값이 공통으로 존재하므로 결과로 3이 출력됩니다.