[C++] 백준 16139 : 인가-컴퓨터 상호작용

문제

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

 

 

 

 

풀이

 각 알파벳별 구간당 누적합을 미리 계산해놓고, 각 질문에 따른 해당 알파벳의 등장 횟수를 출력한다.

 

  - 누적합 구하기

alpha[s[i]-'a'][i]++;         // i번째 문자의 등장 횟수를 증가

 

 

- 질문에 따른 답 출력

alpha[c-'a'][r] - alpha[c-'a'][l-1];         // ㅣ번째부터 r 번째까지 문자 c 가 등장한 횟수

** 이때 l=0 인 경우, 예외처리 필요.

 

코드

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

string s;
int q;
int alpha[28][200001];
int ans[200001];
int main()
{
    cin >> s;
    
    // 각 알파벳의 구간별 누적합 구하기
    alpha[s[0]-'a'][0]++;
    for(int i=1; i<s.size(); i++){
        for(int j=0; j<27; j++){
            alpha[j][i] = alpha[j][i-1];
        }
        alpha[s[i]-'a'][i]++;
    }


    // 각 질문에 따른 결과 출력
    cin >> q;
    for(int i=0; i<q; i++){
        char c;
        int l, r;
        cin >> c >> l >> r;
        if(l == 0 ) ans[i] = alpha[c-'a'][r];
        else ans[i] = alpha[c-'a'][r] - alpha[c-'a'][l-1];
    }

    for(int i=0; i< q; i++) cout << ans[i] << "\n";
    return 0;
}