BOJ 16139 C++

문제 접근

문자열 길이 20만 질문수 20만 400억이므로 그냥 완전탐색으로는 만점을 받을 수 없습니다.
그러므로 누적합을 이용해야 합니다.
이 문제에서는 다음과 같은 누적합 방식을 이용해야 합니다.

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
c: 0 0 0 0 0 0 0 0 0 0 0 0 0
d: 0 0 0 0 0 0 0 0 0 0 0 0 0
e: 0 1 1 1 1 1 1 2 2 2 2 2 2
f: 0 0 0 0 0 0 0 0 0 0 0 0 0
g: 0 0 0 0 1 1 1 1 1 1 1 1 2
h: 0 0 0 0 0 0 0 0 1 1 1 1 1
i: 0 0 0 0 0 0 0 0 0 0 0 0 0
j: 0 0 0 0 0 1 1 1 1 1 1 1 1
k: 0 0 0 0 0 0 0 0 0 0 0 0 0
l: 0 0 0 0 0 0 0 0 0 0 0 0 0
m: 0 0 0 0 0 0 0 0 0 0 0 0 0
n: 0 0 0 1 1 1 1 1 1 1 1 2 2
o: 0 0 0 0 0 0 0 0 0 0 0 0 0
p: 0 0 0 0 0 0 0 0 0 0 0 0 0
q: 0 0 0 0 0 0 0 0 0 0 0 0 0
r: 0 0 0 0 0 0 0 0 0 0 0 0 0
s: 1 1 1 1 1 1 1 1 1 1 1 1 1
t: 0 0 0 0 0 0 0 0 0 0 0 0 0
u: 0 0 1 1 1 1 1 1 1 1 1 1 1
v: 0 0 0 0 0 0 0 0 0 0 0 0 0
w: 0 0 0 0 0 0 0 0 0 1 1 1 1
x: 0 0 0 0 0 0 0 0 0 0 0 0 0
y: 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

예제에서의 배열 “seungjaehwang”의 각 문자들의 값들입니다.
방식을 이러합니다.

문자열을 돌면서 특정 문자가 나오면 그 문자의 카운트 +1 해준다. 나오지 않은 문자들은 전 문자들의 값을 그대로 이어간다.

이렇게 한뒤 주어지는 입력 start와 end를 받아 end인덱스의 값에서 start - 1의 인덱스의 값을 빼주면 값이 나오겠네요.

코드

#include <bits/stdc++.h> 
#define ll long long
using namespace std;


int alp[26][200001];

void setting(string& s)
{
	int len = s.length();
	alp[s[0] - 'a'][0] = 1;
	for (int i = 1; i < len; i++)
	{
		int index = s[i] - 'a';
		for (int j = 0; j < 26; j++)
		{
			alp[j][i] = alp[j][i - 1];
		}
		alp[index][i]++;
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	string s;
	int q;
	cin >> s >> q;
	setting(s);
	while (q--)
	{
		char ch;
		int start, end, index; cin >> ch >> start >> end;
		index = ch - 'a';
		cout << alp[index][end] - alp[index][start - 1] << "\n";
        //start가 0인경우 -1을 하면 쓰레기 값에 접근하므로 오류가 안난다.
	}
}