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

 

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

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

#문제 해결 방법

우선 시간제한을 확인했을때 

매번 매 쿼리마다 구간을 전부 확인하면 시간초과가 난다.

 

알파벳이 나오는 순서가 고정되어있기 때문에

나는 문자열의 길이와 알파벳의 개수만큼의 크기를 가지는 2차원 배열을 선언해서

예 : [string.size()][26] 

문자열의 알파벳 인덱스에 해당하는 열에 카운팅을 해줫다.

[index][알파벳-'a'] +=1 

누적합이기 때문에

r에서 l-1  의 해당하는 알파벳 인덱스를 빼주면

int count = alphaCount[r][alpha - 'a'];
        if (l > 0) {
            count -= alphaCount[l - 1][alpha - 'a'];
        }

구간에서의 나온 알파벳 나온 횟수를 알 수 있다..

는데 기본적인 누적합 원리이다.

설명이 이해가 안된다면 누적합에 대해서 한번 살펴본뒤에

코드를 보면 이해 될 것이다.

 

 

#전체 코드

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

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

    string s;
    cin >> s;

    vector<vector<int>> alphaCount(s.size(), vector<int>(26, 0));

    alphaCount[0][s[0] - 'a'] = 1;

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

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

        int count = alphaCount[r][alpha - 'a'];
        if (l > 0) {
            count -= alphaCount[l - 1][alpha - 'a'];
        }

        cout << count << '\n';
    }

    return 0;
}