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

문제설명

---

입출력 예제

---

개념

　이 문제는 주어진 문자열 내에서 특정 문자가 등장하는 빈도를 특정 구간에서 확인하는 것을 요구한다. 일반적으로, 구간 l에서 r까지 특정 문자 비교를 직접 수행하는 경우, 문자열의 길이가 매우 긴 경우엔 계산 시간이 지나치게 오래 걸릴 수 있으므로 시간 초과 문제에 직면하게 된다. 이러한 문제를 극복하기 위해 '특정 구간'이라는 핵심 키워드에 주목하고, 누적합의 개념을 적용하면 이 문제를 보다 효율적으로 해결할 수 있다.

 

　또한 문자의 등장 횟수를 벡터에 초기화하여 이진 탐색을 통해 구현할 수도 있다.

---

풀이 (1) 이진 탐색

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

vector<int> v[26];
string str;
int T, l, r;
char q;

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> str >> T;

    for (int i = 0; i < str.size(); ++i)
        v[str[i] - 'a'].push_back(i);

    while (T--)
    {
        cin >> q >> l >> r;

        vector<int>& pos = v[q - 'a'];
        auto left = lower_bound(pos.begin(), pos.end(), l);
        auto right = upper_bound(pos.begin(), pos.end(), r);

        cout << right - left << '\n';
    }

　알파벳 각 문자에 대한 등장 위치를 저장하기 위해 벡터 v, 입력 문자열 str, 테스트 케이스의 개수 T, 구간 l, r, 문자 q를 초기화한다. 이렇게 하면 seungjaehwang이라는 문자열을 벡터에 이렇게 저장이 된다.

 

v[0] = 6, 10 // a의 등장 위치가 6, 10
v[4] = 1, 7 // e의 등장 위치가 1, 7
v[6] = 4, 12 // g의 등장 위치가 4, 12
v[7] = 8 // h의 등장 위치가 8
...

　따라서 질문에 해당하는 q의 위치를 담고 있는 v[q - 'a']의 위치를 받아와서, 이진 탐색을 통해 구간 내 개수를 출력하면 해결할 수 있다.

 

풀이 (2) 누적 합

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

string str, tmp;
int T, l, r, sum[26][200001];
char q;

int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> str >> T;

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

    while (T--)
    {
        cin >> q >> l >> r;

        cout << sum[q - 'a'][r + 1] - sum[q - 'a'][l] << '\n';
    }
}

　누적합을 이용하여 2차원 배열 sum[알파벳위치][누적합]을 초기화한 후, 특정 구긴 내 원소의 개수를 구하면 된다.