100일 DSA 코딩 챌린지의 78일차

Source: Dev.to

Introduction

새로운 도전에 도전합니다: 매일 GeeksforGeeks POTD를 풀고 내 풀이를 공유하기! 💻🔥
목표: 문제 해결 능력을 갈고 닦고, 코딩 실력을 향상시키며, 매일 새로운 것을 배우는 것. 내 여정을 따라와 주세요! 🚀

#100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem Statement

정렬된 배열 arr[]와 2차원 배열 queries[][]가 주어집니다. 여기서 queries[i]는 [l, r, x] 형태의 쿼리를 나타냅니다.
각 쿼리마다 부분 배열 arr[l...r]에서 숫자 x가 등장하는 횟수를 구하세요(source).

Examples

Example 1

Input

arr[] = [1, 2, 2, 4, 5, 5, 5, 8]
queries[][] = [[0, 7, 5], [1, 2, 2], [0, 3, 7]]

Output

[3, 2, 0]

Explanation

• 쿼리 [0, 7, 5] → 부분 배열 [1, 2, 2, 4, 5, 5, 5, 8]; 5는 3번 등장합니다.
• 쿼리 [1, 2, 2] → 부분 배열 [2, 2]; 2는 2번 등장합니다.
• 쿼리 [0, 3, 7] → 부분 배열 [1, 2, 2, 4]; 7은 존재하지 않습니다.

Example 2

Input

arr[] = [1, 3, 3, 3, 6, 7, 8]
queries[][] = [[0, 3, 3], [4, 6, 3], [1, 5, 6]]

Output

[3, 0, 1]

Explanation

• 쿼리 [0, 3, 3] → 부분 배열 [1, 3, 3, 3]; 3은 3번 등장합니다.
• 쿼리 [4, 6, 3] → 부분 배열 [6, 7, 8]; 3은 찾을 수 없습니다.
• 쿼리 [1, 5, 6] → 부분 배열 [3, 3, 3, 6, 7]; 6은 1번 등장합니다.

Constraints

• 1 ≤ arr.size(), queries.size() ≤ 10⁵
• 1 ≤ arr[i], x ≤ 10⁶
• 0 ≤ l ≤ r < arr.size()

Solution

from bisect import bisect_left, bisect_right

class Solution:
    def countXInRange(self, arr, queries):
        """
        Returns a list where each element corresponds to the count of x in the
        subarray arr[l...r] for each query [l, r, x].
        """
        res = []
        for l, r, x in queries:
            left = bisect_left(arr, x, l, r + 1)
            right = bisect_right(arr, x, l, r + 1)
            res.append(right - left)
        return res