[LeetCode 3355] Zero Array Transformation I

3355. The Number of Beautiful Subsets

📌 문제 개념

주어진 점수 배열과 query배열이 주어지는데, queries[i] = [li, ri]는 다음을 뜻한다.
1. nums의 [li, ri] 범위에서 subset을 선택.
2. 선택한 인덱스의 값들을 -1 감소
3. 모든 query를 순차적으로 실행하고 nums의 모든 요소가 0이면 true, 아니면 false를 반환.

제약사항
1 <= nums.length <= 10^5

📌 접근 방식

• nums의 길이가 10^5이므로 완전탐색을 사용한 backtracking풀이는 불가능하다.
• 즉 쿼리에 따라서 각 원소의 감소량을 추적하는 방식이 필요하다.
• Difference Array + Prefix Sum을 사용하여 O(n)에 해결 가능

📌 풀이 설명

• 처음에 dp[i]는 nums[i]가 얼마나 감소해야하는지 저장하는 배열이다.
• 이때, queries[i] = [l, r]이면
  • dp[l] -= 1: l부터 감소를 시작한다는 뜻.
  • dp[r+1] += 1: r 이후로부터는 감소가 종료된다는뜻.
• 이후 누적합을 사용하여 nums값을 업데이트.
  • 이를 통해서 해당 index에 감소되는 정확한 양을 구할 수 있음
• 최종적으로 이 dp배열과 nums[i]를 합하여 양수라면 false를 반환한다. (0이 될 수 없는 경우)
  • 여기서 음수여도 성립을 하는데, 그 이유는 query[i]에 해당하는 index의 부분 집합을 선택하는 것이기에, 음수인 것은 0이 되도록 선택을 안한다는 가정을 하면 성립. (양수는 절대로 성립할 수 없다.)

📌 정답

class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int dp[100001] = {0, };

        for(auto vec: queries){
            int l = vec[0];
            int r = vec[1];
            
            dp[l]--;
            dp[r+1]++;
        }

        for(int i = 1; i<nums.size(); i++){
            dp[i] += dp[i-1];
        }

        for(int i = 0 ; i<nums.size(); i++){
            if(nums[i] + dp[i] > 0){
                return false;
            }
        }

        return true;
    }
};