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

 

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

 

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

 

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

첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째

www.acmicpc.net

 

---

 

 

 

해결방안

 

누적 합

 

 

주의할 점

중간에 들어오는 문자가 달라질 수도 있다.

 

---

 

코드

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	string S;
	cin >> S;
 
	vector<vector<int>> v(26, vector<int>(S.length()));
	for (int i = 0; i < S.length(); i++)
	{
		int idx = S[i] - 'a';//문자를 아스키코드 취급하여 인덱스로 만듬
		v[idx][i]++;//해당 알파벳을 가지고 있는 개수만큼 증가
 
		//i=0인 경우 v[j][0]값. 나머지는 누적값.
		if (i > 0)
		{
			for (int j = 0; j < 26; j++)
			{
				v[j][i] = v[j][i] + v[j][i - 1];
			}
		}		
	}
 
 
	char input;
	int n, r1, r2;
	cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		cin >> input >> r1 >> r2;
 
		int index = input - 'a';
 
		if (r1 == 0)
			cout << v[index][r2] << "\n";
		else
			cout << v[index][r2] - v[index][r1-1] << "\n";
	}
 
 
	return 0;
}

 

---