백준 16139 인간-컴퓨터 상호작용 / C++

문제 : 16139

풀이 point

문자열의 구성요소가 영소문자 26개이므로 각 길이마다 빈도수 배열을 구해놓는다.

풀이 방법

각 길이마다 빈도수 배열을 구한다. 만약 abcde라는 문자열이 들어왔다면 길이가 1일때는 a가 1개, 길이가 2일때는 a1개 b1개, 길이가 3일 때는 a1개, b1개, c1개로 구해 나간다.

길이가 N일때는 길이가 N-1일때 구해놓은 문자열 빈도수 + 길이가 N일때 추가되는 문자

코드

//백준 16139, 인간-컴퓨터 상호작용

#include <iostream>

int freq[200'001][26];

int main (){

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    std::string s;
    int N;

    std::cin >> s;

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

    char alpha; int l, r;

    std::cin >> N;

    while(N--){
        std::cin >> alpha >> l >> r;
        std::cout << freq[r+1][alpha-'a'] - freq[l][alpha-'a'] << '\n';
    }

    return 0;
}