[LeetCode] 3152. Special Array II

https://leetcode.com/problems/special-array-ii/description/

leetcode - Special Array II

문제 유형: 이진 탐색

문제 난이도: Medium

 

문제

An array is considered special if every pair of its adjacent elements contains two numbers with different parity.

You are given an array of integer nums and a 2D integer matrix queries, where for queries[i] = [fromi, toi] your task is to check that subarray nums[fromi..toi] is special or not.

Return an array of booleans answer such that answer[i] is true if nums[fromi..toi] is special.

 

배열의 모든 인접한 요소 쌍끼리 홀짝이 다르면, special이라고 여겨진다.

2D배열 queries가 주어진다. queries[i] = [fromi, toi]로 구성된다. 부분배열 nums[fromi, toi]가 special한지 구해야 한다.

각 쿼리들의 응답을 담은 불리언 배열 answer를 반환하시오.

 

풀이

불필요한 연산을 최소화 하기 위해, 이미 어느 쌍들이 special하지 않게 만드는지 구한다.

nums배열을 한 번 순회하면서, 오른쪽에 있는 요소와 홀짝이 같은 경우, 별도의 배열에 쌍의 시작 인덱스를 저장한다.

 

그러고, 각 쿼리를 읽으면서, 각각의 from과 to에 대해서 special을 방해하는 쌍의 인덱스를 담은 배열에서 이진탐색한다.

from에 대해 이진탐색, to에 대해 이진탐색하여 얻는 결과를 각각 l, r이라 한다. to가 닫힌 구간이기에, 별도의 조작 없이 바로 from과 to모두 lower_bound로 찾은 인덱스를 l, r로 하면 된다.

만약 l < r인 경우, 범위 안에 유효하지 않은 쌍이 있는것이다. 그런 경우 false를 답안으로 하고, 아니면, true가 답안이다.

만약 from과 to가 같은 경우는 반드시 true가 답이다.

 

최종 결과 정답 배열을 반환한다.

 

코드

C++

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

        vector<bool> ans;
        for(const auto &query : queries) {
            int from = query[0];
            int to = query[1];

            if(from == to) {
                ans.push_back(true);
                continue;
            }

            int l = lower_bound(notmatchIdx.begin(), notmatchIdx.end(), from) - notmatchIdx.begin();
            int r = lower_bound(notmatchIdx.begin(), notmatchIdx.end(), to) - notmatchIdx.begin();
            if(l < r) {
                ans.push_back(false);
            } else {
                ans.push_back(true);
            }
        }

        return ans;
    }
};