연결 리스트의 헤드(head)가 주어졌을 때, 노드 값의 합이 0이 되는 연속된 노드 구간을 더 이상 존재하지 않을 때까지 반복적으로 삭제하는 문제를 생각해 봅시다. 모든 삭제 작업이 끝난 후에는 최종 연결 리스트의 헤드를 반환해야 합니다.
예를 들어, 연결 리스트가 [1,2,-3,3,1]과 같다면, 2와 -3의 합이 0이므로 이 두 노드가 제거되고, 그 결과는 [3,1]이 됩니다.
문제 해결 접근 방법
이 문제는 누적 합(prefix sum)과 해시 맵(hash map)을 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.
- 값이 0인 더미(dummy) 노드를 생성하고, 더미 노드의 next가 원래 헤드를 가리키도록 설정합니다.
- 정수 키와 ListNode 포인터 값을 저장할 맵(map)을 하나 만들고, 키 0에 더미 노드를 저장합니다. 누적 합 변수 sum은 0으로 초기화합니다.
- 첫 번째 순회에서 head가 NULL이 아닌 동안 다음을 반복합니다.
- sum에 현재 노드의 값을 더하고, m[sum]에 현재 노드를 저장한 뒤, head를 다음 노드로 이동시킵니다.
- head를 다시 더미 노드로 되돌리고, sum도 0으로 초기화합니다.
- 두 번째 순회에서 head가 NULL이 아닌 동안 다음을 반복합니다.
- sum에 현재 노드의 값을 더합니다.
- temp를 m[sum]으로 가져옵니다.
- 만약 temp가 현재 head와 같지 않다면, 두 노드 사이의 구간(합이 0인 구간)을 건너뛰도록 head->next를 temp->next로 변경합니다.
- head를 다음 노드로 이동시킵니다.
- 마지막으로 더미 노드의 next를 반환합니다.
핵심 아이디어: 두 지점의 누적 합이 같다는 것은 그 사이에 있는 노드들의 합이 0이라는 의미입니다. 따라서 맵에 각 누적 합이 마지막으로 나타난 위치를 기록해 두면, 두 번째 순회에서 해당 구간을 한 번에 제거할 수 있습니다.
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;
}
void print_list(ListNode *head){
ListNode *ptr = head;
cout << "[";
while(ptr){
cout << ptr->val << ", ";
ptr = ptr->next;
}
cout << "]" << endl;
}
class Solution {
public:
ListNode* removeZeroSumSublists(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
unordered_map <int, ListNode*> m;
m[0] = dummy;
int sum = 0;
while(head){
sum += head->val;
m[sum] = head;
head = head->next;
}
head = dummy;
sum = 0;
while(head){
sum += head->val;
ListNode* temp = m[sum];
if(temp != head){
head->next = temp->next;
}
head = head->next;
}
return dummy->next;
}
};
main(){
vector<int> v1 = {1,2,-3,3,1};
ListNode *head = make_list(v1);
Solution ob;
print_list(ob.removeZeroSumSublists(head));
}입력
[1,2,-3,3,1]
출력
[3,1]
복잡도 분석
이 알고리즘은 연결 리스트를 두 번 순회하므로 시간 복잡도는 O(n)이며, 누적 합을 저장하기 위한 해시 맵에 추가 공간이 필요하므로 공간 복잡도 역시 O(n)입니다. 단순 반복 삭제 방식보다 훨씬 효율적이라는 점이 이 접근법의 큰 장점입니다.