- 문제 설명
- 문제 풀이
서브테스크가 있는 문제이다. 본래 문제에서는 문자열의 길이가 200,000자 이하, 질문의 수는 200,000개 이하를 조건으로 되어있는데 만약 문자열의 길이가 2,000개 이하, 질문의 수가 2,000개 이하에서만 만족하는 시간복잡도를 갖는다면 50점만 맞는다.
때문에 시간복잡도를 잘 고려해야 하는 문제이고 주의할 점은 O(n^2)을 넘지 않는 것이다.
문자열의 문자가 알파벳 소문자만 있다는 것을 이용해서 범위가 2차원이지만 arr[26][문자열의 길이]를 사용한다.
문자열의 길이만큼인 이유는 최악의 경우 문자열이 모두 같은 알파벳일 수도 있기 때문이다.
반복문을 통해 순차적으로 문자열의 문자들을 검색하고 아스키 코드 값을 이용해 arr[문자 - 97] 인 곳들을 누적합을 이용해 계산한다. 테이블을 보면 다음과 같다
| s | e | u | n | g | j | a | e | h | w | a | n | g | |
| a | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 2 | 2 | 2 |
| b | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| --- | - - - | ||||||||||||
| z | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
각각의 q를 받을때 주어받는 문자, l, r을 기준으로
arr[문자 - 97][r+1] - arr[문자-97][l] 을 출력하면 원하는 출력값이 나오게 된다.
자세한건 코드를 통해 확인할 수 있다. 참고용으로 서브테스크 50점인 코드도 포함했다.
- 코드
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
string S;
int q, l, r;
char alpha;
int arr[26][200001]; // 알파벳 범위 x 문자열 최대 길이(모두 같은 알파벳일 경우 가정)
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> S;
for(int i = 0; i < 26; i++)
for (int j = 1; j <= S.length(); j++)
{
arr[i][j] = arr[i][j - 1];
if (S[j - 1] - 97 == i) // 문자열의 문자 - 97(아스키코드)와 i가 같다면
{
arr[i][j]++;
}
}
cin >> q;
while (q--)
{
cin >> alpha >> l >> r;
cout << arr[alpha - 97][r + 1] - arr[alpha - 97][l] << '\n'; // arr[][0]=0이므로 r+1 부터 l까지
}
return 0;
}
- 코드 (서브테스크 50점)
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string S;
vector<vector<int>> v(26);
int q, l, r, cnt = 0;
char alpha;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> S;
for(int i = 0; i < S.length(); i++)
{
v[S[i] - 97].push_back(i);
}
cin >> q;
while(q--)
{
cnt = 0;
cin >> alpha >> l >> r;
for(int i = 0; i < v[alpha - 97].size(); i++)
{
if(v[alpha - 97][i] >= l && v[alpha - 97][i] <= r)
{
cnt++;
}
}
cout << cnt << '\n';
}
return 0;
}