본문으로 건너뛰기

3355 - Zero Array Transformation I

info

풀이 키워드​

스포주의

누적합


풀이 코드​

info
  • 메모리: 95560 KB
  • 시간: 3 ms
class Solution {
    public boolean isZeroArray(int[] nums, int[][] queries) {
        int[] diff = new int[nums.length+2];
        for (int[] q : queries) {
            ++diff[q[0]];
            --diff[q[1]+1];
        }

        if (diff[0] < nums[0]) return false;
        for (int i = 1; i < nums.length; ++i) {
            diff[i] = diff[i] + diff[i-1];
            if (diff[i] < nums[i]) return false;
        }

        return true;
    }
}

풀이 해설​

대충 생각하면 문제 그대로 query 구간을 1씩 감산해서 판단하는 O(nq)O(nq) 방식이 있다.

하지만 범위를 따졌을 때 105×105=101010^5 \times 10^5 = 10^{10}이어서 해당 시간복잡도는 TLE이므로

prefix sum을 이용하여 효율적으로 처리해주어야 한다.


🌌 무지성 풀이 로직 설명​

  1. query의 연산 정보를 기록할 nums.length + 1 길이의 diff 배열을 생성한다.
  2. query가 a ~ b 구간이라면 diff[a]는 1 더하고, diff[b+1]는 1 뺀다.
  3. diff를 순회하며 이전 칸과 합하고, 해당 합이 대응되는 nums 칸보다 작으면 false를 리턴한다.

🧩 Difference Array​

Difference Array는 누적합을 이용하여 연산 처리를 압축하는 자료구조이다.

예를 들어 0짜리 배열에서 구간을 연산해가며 nums의 값에 도달하는지 확인한다고 했을 때,

query가 {1, 3} 이면

 0  1  2  3  4
[0, 1, 1, 1, 0, ...]

이런식으로 해당 구간의 칸 하나하나에 가산이 들어가야 할 것이다.

하지만 누적합을 이용하면 일일이 가산하지 않고 어느 구간부터 가산을 얼마나 해야 하는지

구간의 시작점만 마킹해서 이를 최적화할 수 있다.

구간의 끝 직후 지점에는 가산 표시를 돌려놔야하므로 -1 처리한다.

 0  1  2  3   4
[0, 1, 0, 0, -1, ...]

따라서 이렇게 시작점과 끝점만 마킹해놓으면 풀이 로직 3번에서 앞 칸과 합하는 과정을 통해

[0, 1, 1, 1, 0, ...]

다시 요렇게 복원된다.

결과적으로 시간복잡도는 O(n+q)O(n + q) 가 된다.


메모​