백준/16139번/인간-컴퓨터 상호작용/실버1

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

문제 설명

Site: Baekjoon
Number: 16139
Category: 누적 합
Rank: Silver 1

처음에 문자열 S(200000자 이하)가 하나 주어지고, 질문의 갯수 N(200000이하)이 주어진다.

이후 N번만큼 질문이 들어오며 하나의 질문에 알파벳 소문자와 두 개의 정수가 입력으로 들어온다.

질문에 대해 출력해야할 내용은 주어진 두 개의 정수 중 첫 번째 정수를 시작 인덱스, 두 번째 정수를 마지막 인덱스로 볼 때 해당 범위에서 알파벳 소문자가 몇 번이 나오는지 출력하는 문제이다.

질문마다 탐색을 진행한다면 200000 * 200000 = 400억이 나오기 때문에 시간초과가 발생한다.

2차원 배열에 문자열 자릿수마다 알파벳 갯수의 누적합을 저장하여 해결하였다.

#include <iostream>

using namespace std;

int arr[26][200001];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	string s;
	cin >> s;

	arr[s[0] - 'a'][0]++;

	for (int j = 1; j < s.length(); j++)
	{
		arr[s[j] - 'a'][j]++;
		for(int i = 0; i < 26; i++)
		{
			arr[i][j] += arr[i][j-1];
		}
	}

	int N;
	cin >> N;

	for(int i = 0; i < N; i++)
	{
		char c;
		int l, r;


		cin >> c >> l >> r;

		if (l == 0)
			cout << arr[c - 'a'][r] << "\n";
		else
			cout << arr[c - 'a'][r] - arr[c - 'a'][l - 1] << "\n";
	}

	return 0;
}