16139번: 인간-컴퓨터 상호작용

2559번: 수열

사용 언어: C++

문제 요약

문자열 S와 질의 Q개가 주어진다. 각 질의는 알파벳 α와 정수 l, r로 구성되어 있으며,

문자열 S[l]부터 S[r]까지 구간 내에서 α가 몇 번 등장했는지 구해야 한다.

• 문자열 길이 ≤ 200,000
• 질의 개수 ≤ 200,000
  ⇒ 단순 순회는 시간 초과 발생.

풀이

구간 빈도 문제에서는 누적합을 사용하면 효율적으로 문제를 풀 수 있다.

알파벳은 총 26개이므로 각 알파벳마다 문자열의 접두 구간에서 누적 등장 횟수를 저장.

prefix[c][i] = 문자열 S의 0번째부터 i-1번째까지의 알파벳 c가 등장한 횟수

그리고 전처리 방식

for (int i = 0; i < S.length(); i++) {
    for (int c = 0; c < 26; c++) { // 모든 알파벳에 대해
        prefix[c][i + 1] = prefix[c][i]; // 이전 값을 그대로 복사
    }
    prefix[S[i] - 'a'][i + 1]++; // 현재 문자의 알파벳만 1 증가
}

정답 코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    string S;
    cin >> S;
    int N = S.length();

    vector<vector<int>> prefix(26, vector<int>(N + 1, 0));

    for (int i=0; i<N; i++) 
    {
        for (int c=0; c<26; c++) 
        {
            prefix[c][i + 1] = prefix[c][i];
        }
        prefix[S[i] - 'a'][i + 1]++;
    }

    int q;
    cin >> q;
    while (q--) 
    {
        char ch;
        int l, r;
        cin >> ch >> l >> r;
        int c = ch - 'a';
        cout << prefix[c][r + 1] - prefix[c][l] << "\n";
    }

    return 0;
}