문제 개요
고유한 정수 값들로 이루어진 연결 리스트의 헤드(head) 노드가 주어집니다. 추가로, 연결 리스트에 포함된 값들의 부분 집합인 리스트 G도 함께 주어집니다.
이때 G 내부에서 두 값이 연결 리스트 상에서 연속적으로 나타난다면 서로 '연결되어 있다'고 정의합니다. 우리가 구해야 할 것은 바로 G에 존재하는 연결 요소(connected components)의 개수입니다.
예시
연결 리스트가 [0, 1, 2, 3]이고 G = [0, 1, 3]이라면 결과는 2입니다. 0과 1은 리스트에서 연속적으로 등장하므로 하나의 그룹으로 묶이고, 3은 별도의 그룹을 이루기 때문에 최종적으로 [0, 1]과 [3], 두 개의 연결 요소가 만들어집니다.
해결 전략
핵심 아이디어는 간단합니다. 연결 리스트를 순차적으로 탐색하면서, 현재 노드의 값이 G에 속하는지 확인하고, 새로운 연결 구간이 시작될 때마다 카운트를 증가시키는 것입니다.
알고리즘 단계
- 결괏값
ret을 0으로 초기화하고, 집합(set)s를 생성한 뒤 G의 모든 원소를 삽입합니다. - 플래그 변수
flag를false로 초기화합니다. head가 NULL이 아닌 동안 다음을 반복합니다.- 현재 노드의 값을
x에 저장합니다. s에x가 존재한다면:flag가false라면(새로운 구간의 시작)ret을 1 증가시킵니다.flag를true로 설정합니다.
x가 존재하지 않는다면flag를false로 되돌립니다.head를 다음 노드로 이동시킵니다.
- 현재 노드의 값을
- 최종적으로
ret을 반환합니다.
이 방식은 연속된 구간의 시작 지점만 정확히 감지하므로, 전체 리스트를 한 번만 순회하면 됩니다. 시간 복잡도는 O(n), 공간 복잡도는 O(m)(m은 G의 크기)입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
class Solution {
public:
int numComponents(ListNode* head, vector<int>& G) {
int ret = 0;
set < int > s;
for(int i = 0; i < G.size(); i++)s.insert(G[i]);
bool flag = false;
while(head){
int x = head->val;
if(s.count(x)){
if(!flag) ret++;
flag = true;
}else flag = false;
head = head->next;
}
return ret;
}
};
main(){
vector<int> v1 = {0,1,2,3};
vector<int> v2 = {0,1,3};
ListNode *h1 = make_list(v1);
Solution ob;
cout << (ob.numComponents(h1, v2));
}실행 결과
입력
[0,1,2,3] [0,1,3]
출력
2
마무리
이 문제는 연결 리스트 순회와 해시 기반 집합 조회를 조합하면 효율적으로 해결할 수 있습니다. 플래그 변수를 활용해 '새로운 연결 구간의 시작'만 카운트하는 패턴은 비슷한 유형의 구간 탐색 문제에서도 유용하게 응용될 수 있으니 꼭 기억해 두세요.