[Leetcode] 3355. Zero Array Transformation I

보자마자 Segment Tree Lazy Update 문제네! 하고 접근했습니다.

2시간을 꼼지락 거리다가 반례를 만나고서야 이게 아니네 싶었습니다.

그리고 늦은 시간이라 자야겠다고 눕는 순간 풀이가 떠올랐습다.

과장 조금 보태서 떠오른 풀이로 1분만에 풀었다

 

우선 Lazy Update 가 안 되는 이유를 보겠습니다.

아래와 같은 상태에서 (1, 3) 이라는 쿼리가 들어왔다고 가정하겠습니다.

이 문제는 합을 구하는게 아니라 범위에 -1을 수행해 0을 만들 수 있는지를 확인하는 것이 목적입다.

따라서, 1번과 2번에는 -1이 들어가지 않고, 3번에만 -1이 수행되어 최상위 노드 값은 0이 아닌 2가 됩니다.

 

그럼 어떻게 풀어야 할까요?

올 해 3월 똑같은 문제를 풀었던 기억이 스쳤습니다.

 

2025.03.24 - [Problem Solving/Leetcode] - [Leetcode] 3356. Zero Array Transformation Ⅱ

[Leetcode] 3356. Zero Array Transformation Ⅱ

 

풀이가 아주 똑같습니다.

정말 부끄러운 점은 그 때도 똑같이 불나방처럼 생각하고 달려들었네요.

당시에도 Segment Tree 에 Lazy Update 로 오해했음

 

억울하면서도 부끄러워서 문제 설명는 더 적지 않으려고 합니다.

겸손한 마음이 들어서 어울리지 않게 문장도 존댓말로 마무리하고 있구요.

그래도 어느 정도 동작하는 Segment Tree 풀이(물론 오답)와 아주 짧은 정답 풀이로 글 마무리합니다.

완전 이 짤이랑 똑같은 상황

 

Segment Tree with Lazy Update

class Solution:
    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
        N = len(nums)
        tree = [0] * (N * 4)
        lazy = [0] * (N * 4)

        self.init(tree, nums, 1, 0, N - 1)
        for qs, qe in queries:
            self.query(tree, lazy, 1, 0, N - 1, qs, qe)
        
        return tree[1] == 0

    def init(self, tree:List[int], nums:List[int], n:int, s:int, e:int):
        if s == e:
            tree[n] = nums[s]
            return
        
        m = (s + e) // 2
        self.init(tree, nums, n * 2, s, m)
        self.init(tree, nums, n * 2 + 1, m + 1, e)
        tree[n] = tree[n * 2] + tree[n * 2 + 1]

    def lazy_check(self, tree:List[int], lazy:List[int], n:int, s:int, e:int):
        if lazy[n] == 0:
            return
        
        tree[n] = max(0, tree[n] - lazy[n])

        if s != e:
            m = (e + s) // 2
            lazy[n * 2] = lazy[n * 2] + m - s + 1
            lazy[n * 2 + 1] = lazy[n * 2] + e - (m + 1) + 1

        lazy[n] = 0

    def query(self, tree:List[int], lazy:List[int], n:int, s:int, e:int, qs:int, qe:int):
        self.lazy_check(tree, lazy, n, s, e)

        if qs <= s and e <= qe:
            tree[n] = max(0, tree[n] - (e - s + 1))

            if s != e:
                m = (s + e) // 2
                lazy[n * 2] = lazy[n * 2] + m - s + 1
                lazy[n * 2 + 1] = lazy[n * 2] + e - (m + 1) + 1  
            return

        if qe < s or e < qs:
            return

        m = (s + e) // 2
        self.query(tree, lazy, n * 2, s, m, qs, qe)
        self.query(tree, lazy, n * 2 + 1, m + 1, e, qs, qe)

        tree[n] = tree[n * 2] + tree[n * 2 + 1]
        return

 

Array Recovery

class Solution:
    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
        L = len(nums)
        dp = [0] * (L + 1)

        for qs, qe in queries:
            dp[qs] += 1
            dp[qe + 1] -= 1

        token = 0
        for i in range(L):
            token += dp[i]

            if token < nums[i]:
                return False
        
        return True