C++ 배열 범위 쿼리: 값과 빈도가 동일한 요소 개수 구하기

이 글에서는 흥미로운 문제 하나를 살펴보겠습니다. N개의 요소로 구성된 배열이 주어졌을 때, 다음과 같은 형식의 쿼리 Q를 처리해야 합니다.

Q(start, end) — start부터 end까지의 구간에서 어떤 수 'p'가 정확히 'p'번 등장하는 경우의 개수를 구합니다.

문제 이해하기

배열이 {1, 5, 2, 3, 1, 3, 5, 7, 3, 9, 8}과 같다고 가정하고, 몇 가지 쿼리를 확인해 보겠습니다.

• Q(1, 8) — 해당 구간에서 1은 한 번, 3은 세 번 등장합니다. 즉 값과 빈도가 일치하는 수는 1과 3 두 개이므로 답은 2입니다.
• Q(0, 2) — 해당 구간에서 1은 한 번만 등장합니다. 따라서 답은 1입니다.

알고리즘

query(s, e)의 동작 과정은 다음과 같습니다.

시작
    s부터 e까지의 요소를 순회하며 각 요소의 빈도를 맵(map)에 저장한다
    count := 0
    맵의 각 키-값 쌍 p에 대해 반복한다
        만약 p.key = p.value 라면 (요소의 값과 빈도가 동일하면)
            count := count + 1
    count 값을 반환한다
끝

C++ 구현 예제

#include <iostream>
#include <map>
using namespace std;

int query(int start, int end, int arr[]) {
    map<int, int> freq;
    // 구간 내 요소들의 빈도를 계산하여 맵에 저장
    for (int i = start; i <= end; i++)
        freq[arr[i]]++;
    int count = 0;
    // 값(key)과 빈도(value)가 일치하는 경우 카운트 증가
    for (auto x : freq)
        if (x.first == x.second)
            count++;
    return count;
}

int main() {
    int A[] = {1, 5, 2, 3, 1, 3, 5, 7, 3, 9, 8};
    int n = sizeof(A) / sizeof(A[0]);
    int queries[][2] = {
        { 0, 1 },
        { 1, 8 },
        { 0, 2 },
        { 1, 6 },
        { 3, 5 },
        { 7, 9 }
    };
    int query_count = sizeof(queries) / sizeof(queries[0]);
    for (int i = 0; i < query_count; i++) {
        int start = queries[i][0];
        int end = queries[i][1];
        cout << "Answer for Query " << (i + 1) << " = " << query(start, end, A) << endl;
    }
}

실행 결과

Answer for Query 1 = 1
Answer for Query 2 = 2
Answer for Query 3 = 1
Answer for Query 4 = 1
Answer for Query 5 = 1
Answer for Query 6 = 0

시간 복잡도 분석

각 쿼리마다 구간의 모든 요소를 순회하며 맵을 구성해야 하므로, 단일 쿼리의 시간 복잡도는 O(N log N)입니다(여기서 N은 구간의 길이). 따라서 Q개의 쿼리를 모두 처리할 때 전체 시간 복잡도는 O(Q × N log N)이며, 빈도 정보를 저장하기 위한 공간 복잡도는 O(N)입니다.