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

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

문제

---

승재는 인간-컴퓨터 상호작용에서 생체공학 설계를 공부하다가 키보드 자판이 실용적인지 궁금해졌다. 이를 알아보기 위해 승재는 다음과 같은 생각을 했다. 

'문자열에서 특정 알파벳이 몇 번 나타나는지 알아봐서 자주 나타나는 알파벳이 중지나 검지 위치에 오는 알파벳인지 확인하면 실용적인지 확인할 수 있을 것이다.'

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

 

입력

---

첫 줄에 문자열 𝑆가 주어진다. 문자열의 길이는 200,000자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 𝑞가 주어지며, 문제의 수는 1 ≤ 𝑞 ≤ 200,000을 만족한다. 세 번째 줄부터 (𝑞+2)번째 줄에는 질문이 주어진다. 각 질문은 알파벳 소문자 𝛼_𝑖와 0 ≤ 𝑙_𝑖 ≤ 𝑟_𝑖< |𝑆|를 만족하는 정수 𝑙_𝑖,𝑟_𝑖가 공백으로 구분되어 주어진다.

 

출력

---

각 질문마다 줄을 구분해 순서대로 답변한다. 𝑖번째 줄에 𝑆의 𝑙_𝑖번째 문자부터 𝑟_i번째 문자 사이에 𝛼_𝑖가 나타나는 횟수를 출력한다.

 

서브태스크 1 (50점)

---

문자열의 길이는 2,000자 이하, 질문의 수는 2,000개 이하이다.

 

서브태스크 2 (50점)

---

추가 제한 조건이 없다.

 

문제 풀이

---

누적합 문제.

 

각 인덱스까지 각 알파벳이 몇 번 등장하는지를 |𝑆+1|*26 칸의 2차원 배열로 저장하면 된다. 배열의 i=0인 26개 칸인 초기화 값인 0을 저장한다. 각 인덱스의 문자가 알파벳의 몇번째인지 구한 후 이전 배열의 값( [i][알파벳의 인덱스] )을 불러와 해당 값에 1을 더해준다. 나머지는 그대로 사용한다.

 

아래는 코드.

#include <iostream>
using namespace std;

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

	int start, end;
	int N;
	char a;
	string str;
	cin >> str;
	cin >> N;
	int length = str.length();
	int** alphabets = new int*[length+1];
	for (int i = 0; i < length+1; i++)
	{
		alphabets[i] = new int[26];
		for (int j = 0; j < 26; j++)
		{
			alphabets[i][j] = 0;
		}
	}
	for (int i = 0; i < length; i++)
	{
		int index = str.at(i) - 97;
		for (int j = 0; j < 26; j++)
		{
			if (j == index)
			{
				alphabets[i + 1][j] = alphabets[i][j]+1;
			}
			else
			{
				alphabets[i + 1][j] = alphabets[i][j];
			}
		}
	}
	for (int i = 0; i < N; i++)
	{
		cin >> a >> start >> end;
		int index = a - 97;
		cout << alphabets[end+1][index] - alphabets[start][index]<<"\n";
	}
	return 0;
}