[16139] 인간-컴퓨터 상호작용

---

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

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

2차원 배열 누적합 문제이다.

알고리즘은 맞았는데 마지막에서 삽질해서 시간이 조금 걸렸다.

 

S[i][j] : 0~i까지 알파벳 j의 누적합

으로 설정했다.

 

알파벳 j는 입력을 받은 후 아스키 코드에 맞춰 97을 빼주고 계산하였다.

 

누적합을 구하는 건  금방했는데, 구간별 누적합을 구하는 데에 오랜 시간이 걸렸다.

l이 들어올 때 0이면 처음부터 탐색하는 것이므로 l=0,

0보다 크면 S[l-1][index]로 설정하였다.

 

전체 코드는 아래에 있다.

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

string A;
int S[200001][26];
// S[i][j] : 0~i까지 알파벳 j의 누적합
int q;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> A;

	for (int i = 0; i < A.length(); i++) {
		int j = A[i] - 97; 
		if (i != 0) {
			for (int k = 0; k < 26; k++) {
				S[i][k] = S[i - 1][k]; 
			}
		}
		S[i][j]++;
	}

	cin >> q;
	for (int i = 0; i < q; i++) {
		char input; int r, l;
		cin >> input;
		cin >> l >> r;
		int index = input - 97;

		int large = S[r][index];
		int small = (l > 0) ? S[l - 1][index] : 0; // 0부터 시작하면 첫 부분부터 탐색하는 것임

		printf("%d\n", large - small);
	}
}