[2024] day 73. Leetcode 1171. Remove Zero Sum Consecutive Nodes from Linked List

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 12일 (화)
Leetcode daily problem

1171. Remove Zero Sum Consecutive Nodes from Linked List

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

Problem

연결리스트 head가 주어질 때, 연결리스트의 내의 연속된 노드의 합이 0이 되면 해당 노드들을 제거한다. 그리고 제거된 연결리스트를 반환한다.

예를 들어 연결 리스트 head = [1,2,-3,3,1]이 있는 경우
1->2-> 에서 -3을 만났을 경우 연속된 3과 -3이 만나므로 1,2,-3, 을 제거하고 나머지 3->1 로 이동해 최종 아웃풋은 [3,1]이 된다.
혹은 1->2 까지 이동했다가 -3과 3이 만났을 때 0이되므로 제거하고 [1,2,1] 을 반환한다.

예제케이스 1에서의 답은 [3,1] 혹은 [1,2,1] 이다.

Solution

linked list

먼저 주어진 연결리스트의 각 노드에 대한 누적합을 계산하여, 각 부분 리스트의 합을 쉽게 확인하도록한다. 그리고 누적합과 해당 합이 달성된노드를 맵에 저장한다. 해쉬맵을 사용해서 누적합을 저장하고 누적합에 저장하는 노드를 연결리스트에 저장한다.
추후 이 누적합을 사용해서 합이 0이 되는 부분의 리스트를 찾고 해당 부분의 리스트를 제거하는 형식으로 해결한다.

Code

class Solution:
    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prefixSum = 0
        prefixSumMp = {}
        dummy = ListNode(0)
        dummy.next = head
        cur = dummy
        
        while cur:
            prefixSum += cur.val
            prefixSumMp[prefixSum] = cur
            cur = cur.next
        
        cur = dummy
        prefixSum = 0

        while cur:
            prefixSum += cur.val
            cur.next = prefixSumMp[prefixSum].next
            cur = cur.next
        
        return dummy.next

Complexicity

시간 복잡도

첫 번째 while 루프에서 연결 리스트를 순회하며 prefixSumMp에 각 노드의 누적 합과 해당 노드를 매핑 할 때 연결리스트의 길이인 O(n) 시간이 소요된다.
뒤 while 루프에서도 연결리스트를 순회해서 prefixSumMp를 사용하여 누적 합이 0이 되는 첫 번째 노드를 찾을때의 시간도 O(n)이 소요되어, 전체적으로 O(N)의 시간 복잡도를 가진다.

공간 복잡도

prefixSumMp라는 map으로 누적 합과 해당 노드를 매핑한다.
해당 맵은 최대 n개의 항목을 가지므로 O(n)의 복잡도를 가진다.