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

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

www.acmicpc.net/problem/16139

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

 

 

 문제

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

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

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

 

 입력

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

 

 출력

 각 질문마다 줄을 구분해 순서대로 답변한다. i번째 줄에 S의 li번째 문자부터 ri번째 문자 사이에 αi가 나타나는 횟수를 출력한다.

 

 

 풀이

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	string s; cin >> s;
	
	int sum[26][200001] = {0,};
	for(int i=0;i<s.length();i++){
		sum[s[i] - 'a'][i+1]++;
	}
	
	for(int i=1;i<=s.length();i++){
		for(int j=0;j<26;j++){
			sum[j][i] = sum[j][i-1] + sum[j][i];
		}
	}
	
	int n; cin >> n;
	for(int i=0;i<n;i++){
		char a; cin >> a;
		int b, c; cin >> b >> c;
		cout << sum[a - 'a'][c+1] - sum[a - 'a'][b] << '\n';
	}
	
	return 0;
}

 일단 문자열을 받고 i번째 위치까지 알파벳들이 몇개나 나왔는지 세어주고 누적합 문제로 풀면 된다. 2차원 배열을 만들어서 행은 문자를 의미하고 열을 해당문자의 카운팅 수로 진행하면 된다.