[2024] day 187. Leetcode 2181. Merge Nodes in Between Zeros

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

2024년 7월 4일 (목)
Leetcode daily problem

2181. Merge Nodes in Between Zeros

https://leetcode.com/problems/merge-nodes-in-between-zeros/?envType=daily-question&envId=2024-07-04

Problem

Solution

Recursion

현재 노드의 값을 0으로 설정하고, linked list의 배열을 반복해 다음 0을 만날 때까지 값을 더하면서 노드의 합을 계산한다
포인터는 다음 블록의 시작 시점에 있어야하고, 새로운 linked list는 원래 linked list아ㅗ 유사하지만 계산해야 할 블록이 하나 적어진다.
따라서, 이 포인터를 재귀함수에 새로운 하위 문제로 전달한다.

첫 번째가 0이 아닌 head의 next (다음 노드)를 head에 저장하고, 루프라 끝나는 조건은 head가 null이 됐을 때 (마지막 노드가 없을 때) 이다.
head를 가지는 더미 노드를 초기화하고, 더해가는 합을 초기값을 0으로 한다.
그 후 더미 노드의 값이 0이 아닐 때까지 더미 노드의 값을 더해하고, 더미 노드를 다음 노드로 이동시켜 나간다.
루프가 끝나면 head를 반환한다.

Code

class Solution:
    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        head = head.next
        if not head:
            return head
        
        dummy = head
        cur_sum = 0
        while dummy.val != 0:
            cur_sum += dummy.val
            dummy = dummy.next
            
        
        head.val = cur_sum
        head.next = self.mergeNodes(dummy)
        
        return head

Complexicity

시간 복잡도

주어진 linked list를 처음부터 끝까지 탐색하므로 시간복잡도는 O(n) 이다.

공간 복잡도

재귀가 돌면서 재귀를 위한 스택 공간이 필요하므로 linked list의 원소의 수만큼 재귀가 돌기 때문에 전체 공간 복잡도는 O(n)이다.