백준 16139번: 인간-컴퓨터 상호작용 (C++)

https://www.acmicpc.net/problem/16139

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

 

 

풀이

최대 시간복잡도가 질문 수 200,000 *  문제 수 200,000 이기 때문에 100점을 맞기 위해서는 완전탐색으로는 무리가 있다.

탐색 했던 곳을 재탐색할 필요가 없기 때문에 누적합을 이용했다.

 

한번의 탐색으로 각 구간별 알파벳의 갯수를 누적합으로 저장했다.

그리고 L ~ R 구간을 구할 때 누적합으로 저장된 R - 1 번째 항에서 L 번째 항을 빼면 L ~ R 구간의 알파벳 개수가 된다.

 

하지만 0번째 항을 뺄 때 오버플로우가 문제였다.

그래서 초기에 alpha 백터에 0을 전부 넣어서 오버플로우를 방지했다.

 

전체 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s;
    vector<vector<int>> alpha;
    int q;

    alpha.resize(26);
    for (int i = 0; i < 26; i++) alpha[i].push_back(0);

    cin >> s;

    for (int i = 0; i < s.size(); i++) {
        for (int j = 0; j < 26; j++) {
            alpha[j].push_back(alpha[j][i]);
        }
        alpha[s[i] - 'a'][i + 1]++;
    }

    
    cin >> q;
    while (q--) {
        char a;
        int s, e;
        cin >> a >> s >> e;
        cout << alpha[a - 'a'][e + 1] - alpha[a - 'a'][s] << '\n';
    }
}