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

문제 링크

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

 

풀이

각 알파벳마다 누적합을 구하는 문제
개행할 때 \n을 써주어야 하고, 누적합 구할 때 난 현재 인덱스부터 문자열 끝까지를 갱신해줬는데, 이렇게 하면 시간 초과가 나는 듯 하다.

1. 입력받은 문자열 s를 하나씩 돌면서 각 알파벳의 누적합을 구해준다.
   1. 현재 인덱스의 a~z의 누적합을 갱신해주고, 현재 알파벳은 +1해준다.
2. 질문을 입력 받으면서, stt-1이 0보다 작다면 alpha[c-'a'][end]를, 아니라면 alph[c-'a'][end] - alpha[c-'a'][stt-1]을 출력한다.

 

코드

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

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

    string s;
    cin >> s;
    int n;
    cin >> n;

    vector<vector<int>> alpha(26, vector<int>(s.size()));
    for (int i = 0; i < s.size(); i++) // 누적합 구해주기
    {
        for (int j = 0; j < 26; j++)
        {
            if(i != 0) alpha[j][i] = alpha[j][i - 1];
        }

        alpha[s[i] - 'a'][i] += 1;
    }

    for (int i = 0; i < n; i++)
    {
        char c;
        int stt, end;
        cin >> c >> stt >> end;
        if (stt - 1 < 0)
        {
            cout << alpha[c - 'a'][end] << '\n';
        }
        else
        {
            cout << alpha[c - 'a'][end] - alpha[c - 'a'][stt - 1] << '\n';
        }
    }

    return 0;
}