[LeetCode] 3152. Special Array II (Python)

 

난이도: 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] = [from_i, to_i] your task is to check that subarray nums[from_i..to_i] is special or not.

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

 

문제 예제

---

Example 1:

Input: nums = [3,4,1,2,6], queries = [[0,4]]
Output: [false]
Explanation:
The subarray is [3,4,1,2,6]. 2 and 6 are both even.

Example 2:

Input: nums = [4,3,1,6], queries = [[0,2],[2,3]]
Output: [false,true]
Explanation:
The subarray is [4,3,1]. 3 and 1 are both odd. So the answer to this query is false.
The subarray is [1,6]. There is only one pair: (1,6) and it contains numbers with different parity. So the answer to this query is true.

 

제한 사항

---

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 2
• 0 <= queries[i][0] <= queries[i][1] <= nums.length - 1

 

✏️ Solution(솔루션)

---

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        n = len(nums)
        false_list = []
        answer = []

        for i in range(n-1):
            if (nums[i] % 2 == 0 and nums[i+1] %2 == 0) or (nums[i] % 2 != 0 and nums[i+1] %2 != 0):
                false_list.append((i, i+1))

        false_cnt = len(false_list)

        for query in queries:
            left, right = 0, false_cnt-1
            false_check = True
            while left <= right:
                mid = (left+right)//2
                if query[0] <= false_list[mid][0] <= query[1] and query[0] <= false_list[mid][1] <= query[1]:
                    false_check = False
                    break
                elif false_list[mid][1] <= query[0]:
                    left = mid+1
                else:
                    right = mid-1
            
            answer.append(false_check)
        
        return answer

 

문제를 계속 읽어봤을 때 nums[queries[i][0]:queries[i][1]]에 False를 만족하는 숫자 pair가 하나라도 있으면 False를 저장하고 아니면 True를 저장하면 될 것 같았다.

 

그래서 먼저 nums의 요소를 보면서 조건을 만족하는지 안하는지 체크하고 만약 조건을 만족하지 않는다면 false_list에 (i, i+1)을 저장했다.

 

그리고, 각 query마다 false_list에 다음을 만족하는 (index, index+1)이 있는지 이진탐색으로 확인했다.

query[0] <= false_list[mid][0] <= query[1] and query[0] <= false_list[mid][1] <= query[1]

 

만약 위 조건을 만족하면 현재 쿼리에 대해 False를 저장하고, 아니라면 True를 저장했다.

 

이렇게 정답을 맞출 수 있었다.

---

[LeetCode] 3152. Special Array II