Special Array II

오늘 컨테스트 문제를 풀다가 머리가 좀 띵했던 문제였다. 문제 설명 자체는 쉬웠고 quereis 벡터 안에 오는 숫자의 Range 안에 Special Array 가 생성이 되는지를 물어본 문제인데 당연스럽게도 Brute Force 로 풀면은 TLE 가 나오는 문제다.

그래서 이 문제를 효율적으로 풀기 위해서는 어떻게 해야할까 고민하다가 확실히 누적된 어떤 값을 사용하면 좋겠다 싶어서 prefix 접근을 했으나 보기 좋게 망해버렸다.

prefix 접근을 통한 방법은 맞았지만, 어떻게 잘 사용할 수 있을지를 너무 잘못했다. 해답을 봤을 떄, prefix sum 을 사용해서 Special Array 로 만들어지는 구간에 +1을 하고, 구간이 아니라면은 전에 있는 값을 그대로 가지고 왔다.

이후에는 Queries 안에 Range 를 종합해서 그 구간에 Special Array 가 이어지는 구간인지 확인할 수 있게 되었고 정답이었다.

정답률이 굉장히 낮았는데 prefix sum 을 굉장히 잘 구현해야지 풀 수 있었을거같다.

class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
        vector<bool> answer; 
        vector<int> prefix(nums.size(), 0); 
        for(int i = 1; i < nums.size(); i++){
            if((nums[i] % 2) == (nums[i-1] % 2)){
                prefix[i] = prefix[i-1]; 
            } else{
                prefix[i] = prefix[i-1] + 1; 
            }
        }

        for(vector<int>& v : queries){
            int start = v[0], end = v[1]; 

            if(prefix[end] - prefix[start] == end - start){
                answer.push_back(true); 
            } else{
                answer.push_back(false); 
            }
        }

        return answer; 
    }
};