(백준/C++) 16139_인간-컴퓨터 상호작용

개요

16139번: 인간-컴퓨터 상호작용 (acmicpc.net) 문제는 특정 문자열 내에서 주어진 구간에 특정 알파벳이 몇 번 나타나는지 빠르게 구하는 문제로 누적 합 문제 카테고리에 속해 있습니다.

누적 합 문제는 구간에 있는 수의 합을 빠르게 계산하기 위한 방법입니다.

이게 왜 누적 합 문제인지 헷갈릴 수도 있지만, 알파벳이 나타나는 횟수를 물어보기 때문에, 그 횟수가 누적된다고 보시면 이해하기 쉬울 것 같습니다.

이 문제는 $O(26 \cdot N)$의 시간 복잡도로 누적 합 배열을 생성하고, 특정 구간의 횟수를 $O(1)$의 시간 복잡도로 구할 수 있습니다.

로직 설계

이 문제는 각 알파벳별로 특정 구간의 출현 횟수를 빠르게 구해야 하므로, 알파벳별로 누적 합을 저장하는 방법으로 해결할 수 있습니다.

만약 이 문제가 이해가 어려우시다면 11659번: 구간 합 구하기 4 (acmicpc.net) 문제를 먼저 푸시는 것을 추천 드립니다.

관련 포스트 - (백준/C++) 구간 합 구하기 4 풀이

---

풀이

누적 합을 이용하여 주어진 구간의 특정 알파벳의 출현 횟수를 계산하기 위해서는 문자열을 순회하며 각 알파벳별로 누적 합을 저장하면 됩니다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int q;
	string str;
	cin >> str;
	cin >> q;

	vector<vector<int>> alphabet(str.length() + 1, vector<int>(26, 0));

	//누적합 배열 계산
	for (int i = 0; i < str.length(); i++)
	{
		for (int j = 0; j < 26; j++)
		{
			alphabet[i + 1][j] = alphabet[i][j]; //기존 알파벳 누적합 유지
		}
		alphabet[i + 1][str[i] - 'a']++; //추가된 알파벳 누적합 추가
	}

	while (q--)
	{
		char alpha;
		int s, e;
		cin >> alpha >> s >> e;
		//해당 알파벳의 누적합 구간 출력
		cout << alphabet[e + 1][alpha - 'a'] - alphabet[s][alpha - 'a'] << '\n';
	}
}