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

문제

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

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

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

문제풀이

사용한 알고리즘 : 구간합 배열 (Prefix Sum)

(1) 코드 4

 'pSum[i][x] : 'x' 라는 알파벳이 0~i 사이 몇 번 등장하는 횟수' 라고 설정하였습니다.
 각 알파벳은 a : 0 , b : 1 , ... , z : 25 의 index 를 주었습니다.

(2) 코드 10~18

 과정 (1) 에서 만든 배열의 값을 구합니다.

(3) 코드 21~31

 구간 i~j 사이의 'x' 의 등장 횟수는 pSum[j][x] - pSum[i-1][x] 입니다.

	#include <bits/stdc++.h>
	using namespace std;
	int q, pSum[222222][26];
	string S;
	int main() {ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> S;
	for (int i = 0; i < S.length(); ++i) {
	// 이전꺼 합
	if (i != 0) {
	for (int k = 0; k < 26; ++k)
	pSum[i][k] = pSum[i - 1][k];
	}
	int now = S[i] - 'a';
	pSum[i][now]++;
	}
	cin >> q;
	for (int i = 0; i < q; ++i) {
	char num;
	int l, r;
	cin >> num;
	cin >> l >> r;
	int now = num - 'a';
	int p1 = l > 0 ? pSum[l - 1][now] : 0;
	int p2 = pSum[r][now];
	cout << p2 - p1 << '\n';
	}
	return 0;
	}

view raw BOJ 16139.cpp hosted with ❤ by GitHub