[Algorithm][LeetCode 3355][Medium] Zero Array Transformation I

이번 문제는 차분 배열(Difference Array) 개념을 활용하여, 수많은 구간 쿼리를 빠르게 처리할 수 있는지 평가하는 문제다.
초기 풀이 방식에서 성능 개선을 거쳐 AI가 최종 추천하는 1-pass 최적화 방식까지 3단계로 접근 방법을 소개한다.

문제 설명

정수 배열 nums와 2차원 배열 queries가 주어진다. 각 쿼리는 [li, ri] 형태로, 해당 구간에서 원하는 일부 인덱스를 선택하여 값을 1만큼 감소시킬 수 있다.
모든 쿼리를 순서대로 처리한 후, 모든 원소가 0인 배열로 만들 수 있는지 여부를 판단해야 한다.

접근 1단계: 초기 코드 (직접 반복)

각 쿼리 범위를 직접 순회하며, 각 인덱스가 몇 번 감소할 수 있는지를 map에 기록하는 방식이다.

var isZeroArray = function(nums, queries) {
    const map = {};
    for (let query of queries) {
        let [start, end] = query;
        while (end >= start) {
            map[end] = map[end] ? map[end] + 1 : 1;
            end--;
        }
    }

    for (let i = 0; i < nums.length; i++) {
        if (map[i] && (map[i] < nums[i])) return false;
        if (!map[i] && nums[i] !== 0) return false;
    }
    return true;
};

단점: 쿼리 범위를 직접 순회하기 때문에 O(Q × R)의 시간 복잡도를 가지며, 긴 쿼리나 수많은 입력이 들어오면 시간 초과가 발생한다.

---

접근 2단계: 차분 배열 적용

변화량만 기록한 후 누적합으로 계산하는 차분 배열 (Difference Array)을 적용하면 O(N + Q)으로 시간 복잡도를 줄일 수 있다.

var isZeroArray = function(nums, queries) {
    const n = nums.length;
    const delta = new Array(n + 1).fill(0);

    for (let [left, right] of queries) {
        delta[left]++;
        if (right + 1 < n) delta[right + 1]--;
    }

    const count = new Array(n).fill(0);
    count[0] = delta[0];
    for (let i = 1; i < n; i++) {
        count[i] = count[i - 1] + delta[i];
    }

    for (let i = 0; i < n; i++) {
        if (nums[i] > count[i]) return false;
    }

    return true;
};

장점: 각 구간의 시작과 끝만 업데이트하므로 모든 쿼리를 O(1)로 처리할 수 있다. 누적합을 통해 실제 각 인덱스의 감소 기회를 계산한다.

---

접근 3단계: AI 최적화 코드 (1-pass 누적합)

추가 배열 없이, 누적합과 검증을 하나의 루프에서 처리하여 성능과 메모리 사용량을 동시에 최적화한다.

var isZeroArray = function(nums, queries) {
    const n = nums.length;
    const delta = new Array(n + 1).fill(0);

    for (let [left, right] of queries) {
        delta[left]++;
        if (right + 1 < n) delta[right + 1]--;
    }

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

최종 형태: 누적합을 저장하면서 바로 검증까지 수행하므로 시간 복잡도 O(N + Q), 공간 복잡도 O(N)의 최적 구조이다.

---

정리

• 초기 풀이: 직관적이지만 느림 (O(Q × N))
• 차분 배열 적용: 빠른 계산 가능 (O(N + Q))
• AI 최적화: 누적합과 검증을 통합하여 성능과 메모리 효율 동시 개선

차분 배열이란?

차분 배열은 어떤 구간 [l, r]에 동일한 연산을 수행해야 할 때, 시작점에만 +1, 끝점 다음에 -1을 기록한 후 누적합을 구해 처리하는 방법이다.
특히 구간 업데이트가 빈번할 때 매우 강력한 도구다.