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

문제

풀이

누적 합 문제이다.

 

O(N * N)이 되면 50점이다. O(N)의 시간복잡도로 해결해야한다.

• 문자열의 처음부터 시작하여 i번째까지 나온 알파벳마다 배열에 저장해둔다. 
• i번째 문자열이 j일 경우, 이전 j가 등장한 횟수에서 + 1한 값을 배열에 저장한다. 
• 그외에는 이전에 등장한 횟수로 저장한다.

코드

#include <iostream>


using namespace std;

int alpha[26][200000];

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

    string S;
    cin >> S;

    // 문자열의 처음부터 시작하여 i번째까지 나온 알파벳을 배열에 저장
    alpha[S[0] - 'a'][0]++;
    for (int i = 1; i < S.size(); ++i)
    {
        for (int j = 0; j < 26; ++j)
        {
            // i번째 문자열이 j일 경우, 이전 j가 등장한 횟수에서 + 1
            if (j == S[i] - 'a')
            {
                alpha[j][i] = alpha[j][i - 1] + 1;
            }
            else
            {
                alpha[j][i] = alpha[j][i - 1];
            }
        }
    }

    int q;
    cin >> q;

    while (q--)
    {
        char a;
        int l, r;
        cin >> a >> l >> r;

        // l부터 r까지 a가 얼마만큼 나왔는지 계산
        if (l == 0)
        {
            cout << alpha[a - 'a'][r] << '\n';
        }
        else
        {
            cout << alpha[a - 'a'][r] - alpha[a - 'a'][l - 1] << '\n';
        }
    }

    return 0;
}