C++에서 부분 문자열 내 문자 빈도 쿼리 처리 방법

문제 이해하기

하나의 문자열과 Q개의 쿼리가 주어집니다. 각 쿼리는 두 개의 정수 l, r과 하나의 문자 ch로 구성되며, 각 쿼리마다 부분 문자열 내에서 해당 문자가 나타나는 빈도를 구하는 프로그램을 C++로 작성하는 것이 이 글의 목표입니다.

문제 설명: 매 쿼리마다 부분 문자열 str[l...r] 범위 안에서 문자 'ch'가 몇 번 등장하는지 그 빈도를 구해야 합니다.

먼저 예제를 통해 문제를 자세히 살펴보겠습니다.

입력

str = "tutorialspoint"
Q = 2
0 6 t
5 13 i

출력

2 2

설명

쿼리 1: 부분 문자열은 "tutoria"이며, 문자 t는 2번 등장합니다.

쿼리 2: 부분 문자열은 "ialspoint"이며, 문자 i는 2번 등장합니다.

방법 1: 단순 순회(Brute Force)

가장 직관적이고 간단한 접근 방식은 각 쿼리마다 문자열의 l 위치부터 r 위치까지 한 글자씩 순회하면서 문자 ch의 등장 횟수를 직접 세는 것입니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;

struct Query{
    int l, r;
    char ch;
};
int CalcCharFreq(string str, Query queries){
    int count = 0;
    for(int i = queries.l; i < queries.r; i++){
        if(str[i] == queries.ch)
            count++;
    }
    return count;
}

int main(){
    string str = "tutorialspoint";
    int Q = 2;
    Query queries[Q];
    queries[0].l = 0;
    queries[0].r = 5;
    queries[0].ch = 't';
    queries[1].l = 5;
    queries[1].r = 13;
    queries[1].ch = 'i';
    for(int i = 0; i < Q; i++)
        cout << "For Query " << (i+1) << ": The frequency of occurrence of character '" << queries[i].ch << "' is " << CalcCharFreq(str, queries[i]) << "\n";
    return 0;
}

실행 결과

For Query 1: The frequency of occurrence of character 't' is 2
For Query 2: The frequency of occurrence of character 'i' is 2

방법 2: 누적 빈도 배열(Prefix Frequency Array) 활용

보다 효율적인 방법은 미리 계산된 배열을 사용하는 것입니다. 여기서는 2차원 배열을 만들어 각 인덱스까지의 문자별 누적 빈도를 저장합니다. 예를 들어 freq[3][2]에는 인덱스 2까지 문자 'c'가 등장한 횟수가 저장됩니다. 초기 상태에서는 모든 빈도 값이 0입니다.

모든 인덱스에 대해 각 문자의 누적 빈도를 먼저 계산한 후, 특정 범위 [l, r] 내 문자의 빈도는 '인덱스 r까지의 누적 빈도 − 인덱스 l까지의 누적 빈도'로 간단히 구할 수 있습니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
int charFreq[100][26];

struct Query{
    int l, r;
    char ch;
};

void countCharFreq(string str, int size){

    memset(charFreq, 0, sizeof(int));
    for (int i = 0; i < size; i++){
        charFreq[i][str[i] - 'a']++;
    }
    for (int i = 1; i < size; i++) {
        for (int j = 0; j < 26; j++)
            charFreq[i][j] += charFreq[i - 1][j];
    }
}


int CalcCharFreq(Query queries){
    return charFreq[queries.r][queries.ch - 'a'] - charFreq[queries.l][queries.ch - 'a'];
}

int main(){
    string str = "tutorialspoint";
    int size = str.length();
    int Q = 2;
    countCharFreq(str, size);
    Query queries[Q];
    queries[0].l = 1;
    queries[0].r = 13;
    queries[0].ch = 't';
    queries[1].l = 4;
    queries[1].r = 13;
    queries[1].ch = 'i';
    for(int i = 0; i < Q; i++)
        cout << "For Query " << (i+1) << ": The frequency of occurrence of character '" << queries[i].ch << "' is " << CalcCharFreq(queries[i]) << "\n";
    return 0;
}

실행 결과

For Query 1: The frequency of occurrence of character 't' is 2
For Query 2: The frequency of occurrence of character 'i' is 2

시간 복잡도 비교

단순 순회 방식은 쿼리 하나를 처리할 때 최대 O(N)의 시간이 걸리므로, 전체 시간 복잡도는 O(Q × N)입니다. 반면 누적 빈도 배열 방식은 전처리 단계에서 O(26 × N)의 시간이 필요하지만, 이후에는 각 쿼리를 O(1)에 처리할 수 있습니다. 따라서 쿼리 개수가 많은 상황일수록 누적 빈도 배열 방식이 훨씬 효율적입니다.