문제설명
입출력 예제
개념
이 문제는 주어진 문자열 내에서 특정 문자가 등장하는 빈도를 특정 구간에서 확인하는 것을 요구한다. 일반적으로, 구간 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[알파벳위치][누적합]을 초기화한 후, 특정 구긴 내 원소의 개수를 구하면 된다.
반응형
'Algorithm > 백준' 카테고리의 다른 글
[백준] 1927 최소 힙 with C++ (0) | 2023.05.22 |
---|---|
[백준] 11279 최대 힙 with C++ (0) | 2023.05.21 |
[백준] 5430 AC with C++ (0) | 2023.05.19 |
[백준] 1021 회전하는 큐 with C++ (0) | 2023.05.18 |
[백준] 10866 덱 with C++ (0) | 2023.05.17 |