[leetcode] 1171. Remove Zero Sum Consecutive Nodes from Linked List

문제 : https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/

---

링크드리스트 문제.

 

링크드리스트를 앞에서부터 탐색하면서 현재까지의 sum을 key, ListNode*을 value로 하는 map을 만들어서 저장해간다.

1, 3, 2, -3, -2, 5, 5, -5, 1 을 예로 들어보자.

index	1	2	3	4	5	6	7	8	9
array	1	3	2	-3	-2	5	5	-5	1
subsum	1	4	6	3	1	6	11	6	7

합을 구하면 위 표와 같다. 링크드리스트라 인덱스로 표현되지는 않지만 말하기 쉽게 임의로 차례대로 인덱스를 붙여놓았다.

 

1. subsum으로 검색시 map에 없는 경우

인덱스 1~4가 이에 속한다.

이 때는 합이 0이 되는 경우가 없을 때이므로 map에 {subsum, ListNode*}를 저장해간다.

 

2. subsum으로 검색시 map에 있는 경우

인덱스가 5일 때를 보면 subsum(map의 key)이 1이고 이는 인덱스 1에서 이미 나온 값이다. 

그리고 array 값을 보면 인덱스 2~5의 합이 0이다.

즉, subsum으로 map에서 검색했을 때 나온 ListNode(1)의 다음 인덱스(2) ~ 현재 탐색 중인 인덱스(5)는 삭제가 된다.

따라서, 1번 노드 -> 6번 노드로 링크드리스트를 갱신해준다.

사실 중간 노드는 참조되지 않으므로 메모리 할당도 해제해주어야 하지만 코드상에서는 생략했다.

2~5 인덱스에 대해서 나온 subsum은 map에서 삭제해주어야 한다.

그렇지 않은 경우 2~5 노드들은 삭제가 되었지만 6번 인덱스 탐색 시 3번 인덱스가 탐색이 되기 때문이다. (subsum(key)이 같으므로.)

 

위 알고리즘을 적용하기 전에 링크드리스트의 가장 앞에 0을 val로 하는 노드(이게 링크드리스트의 가장 앞에 위치하는 노드가된다.)를 저장해주고 map에는 subsum이 0인 경우 방금 추가한 노드를 보게 한다.

이렇게 해주는 이유는 1, 3, -4 를 예로 들어보면 -4 탐색 시 subsum은 0이 되어 모든 노드가 삭제된다. 

이 때, 방금 말한 처리를 하지 않으면 map에는 0에 대한 값이 없기 때문에 0이 되는 경우이지만 이를 인식하지 못한다.

즉, 모든 노드가 삭제되는 경우 인식하기 위해 0에 대한 처리를 추가해준다.

---

처음에는 unordered_map에 insert를 사용하면 가장 뒤에 저장되는 줄 알고, key값을 sum, value를 노드의 val를 저장했었다.

그래서 map을 모두 세팅 하고나서 map을 돌면서 val로 노드를 만들면서 새로운 linked list를 만들고 이를 반환했다.

그런데 unordered_map은 순서를 보장하지 않는다. 즉, insert를 한다고 해서 가장 뒤에 들어가지는 않는 것이다. 내가 원하던 자료구조가 아니었던 것이다.. 

왜 틀렸는지 몰라서 여기서 시간이 많이 소요되었다.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1171.%20Remove%20Zero%20Sum%20Consecutive%20Nodes%20from%20Linked%20List.cpp