[LeetCode 3355] Zero Array Transformation I

문제개요

문제: https://leetcode.com/problems/zero-array-transformation-i

 

정수 배열 nums와 2차원 배열 queries가 주어집니다. 각 쿼리 queries[i] = [li, ri]는 해당 구간의 모든 인덱스 값을 1씩 감소시키는 작업입니다. 모든 쿼리를 순서대로 처리한 후, 배열의 모든 값이 0이 되는지를 판별하는 문제입니다.

 

예시

Input: nums = [1, 0, 1], queries = [[0, 2]]
Output: true

[0, 2] 구간에서 인덱스 0과 2를 선택하여 각각 1씩 감소시키면, [1, 0, 1] → [0, 0, 0]이 되므로 Zero Array가 됩니다.

접근 방법

이 문제는 누적합(Prefix Sum) 기법을 활용하여 효율적으로 해결할 수 있습니다.

• 각 쿼리는 li에서 -1, ri + 1에서 +1을 적용하여 변화량 배열(prefix) 을 구성합니다.
• 이후, prefix[i] 배열에 누적합을 적용하면 각 인덱스에서 총 얼마나 감소했는지를 알 수 있습니다.
• 최종적으로 각 원소 nums[i] + prefix[i]가 0 이하가 되어야 하며, 0보다 큰 원소가 있다면 Zero Array를 만들 수 없습니다.

누적 변화량의 원리는 다음과 같습니다.

1. prefix[i]는 인덱스 i 위치에서 값이 얼마나 변화해야 하는지 누적 기록합니다.
2. 쿼리 [l, r]에 대해:
   • prefix[l] -= 1 → l부터 값을 감소시킴
   • prefix[r + 1] += 1 → r+1부터는 다시 원상복구시킴 (즉, 감소 효과가 r까지만 미치고 그 이후부터는 영향을 끊기 위함)

 

구현

class Solution {
    public boolean isZeroArray(int[] nums, int[][] queries) {
        int n = nums.length;

        int[] prefix = new int[n+1];

        for (int[] arr : queries) {
            int a=arr[0];
            int b=arr[1];
            prefix[a]--;
            prefix[b+1]++;
        }

        for (int i=1; i<=n; i++) {
            prefix[i] += prefix[i-1];
        }

        for (int i=0; i<n; i++) {
            nums[i] += prefix[i];
            if (nums[i] > 0) {
                return false;
            }
        }
    
        
        return true;
    }
}

 

시간 복잡도 & 공간 복잡도

• 시간 복잡도: O(n + q)
  • n: 배열 nums의 길이
  • q: 쿼리의 개수
• 공간 복잡도:
  • O(n) : prefix 배열 하나만 추가로 사용합니다.