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

문제 요약

승재를 도와 특정 문자열 $S$, 특정 알파벳 $\alpha$와 문자열의 구간 $[l,r]$이 주어지면 $S$의 $l$번째 문자부터 $r$번째 문자 사이에 $\alpha$가 몇 번 나타나는지 구하는 프로그램을 작성하여라. 승재는 문자열의 문자는 $0$번째부터 세며, $l$번째와 $r$번째 문자를 포함해서 생각한다. 주의할 점은 승재는 호기심이 많기에 (통계적으로 크게 무의미하지만) 같은 문자열을 두고 질문을 $q$번 할 것이다.

문제 분류

• 누적 합

문제 풀이

누적 합 배열을 2차원 배열로 선언하여 각 알파벳마다 갱신해주면 된다. cin을 사용하면 시간 초과되어 50점밖에 못받고, scanf()를 써야 완벽하게 풀린다.

풀이 코드

#include <stdio.h>
#include <iostream>

using namespace std;

int S[200000][26];

int main() {
	char in;
	int q, s, e;
	for (int i = 1;; i++) {
		scanf("%c", &in);
		if (in == '\n') break;
		for (int j = 0; j < 26; j++)
			S[i][j] = S[i - 1][j];
		S[i][in - 'a']++;
	}
	scanf("%d", &q);
	while (q--) {
		scanf(" %c %d %d", &in, &s, &e);
		printf("%d\n", S[e + 1][in - 'a'] - S[s][in - 'a']);
	}
	return 0;
}