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

📌 문제

내용을 직관적이게 정리하자면,

문자열 S가 주어지고, 테스트 케이스 q 를 입력 받으면

문자열 S 내 l번째 ~ r번째 문자 내에 문자 a가  몇 개 있는지 케이스 별로 출력하는 문제이다.

조건은 문자열은 20만자 이하, 테스트 케이스 수는 20만개이다.

 

이게 문제라고? 너무 쉽잖아 그냥 반복문으로 계산하면 되지 않을까? 라고 생각할 순 있지만, 테스트 케이스의 개수와 문자열의 개수를 보자. 테스트케이스마다 문자열을 탐색하면 시간복잡도가 기하급수적으로 증가하여 비효율적이다.

 

이 문제는, 결론을 먼저 말하자면 누적합 문제이다.

누적합은 빈도수나 구간 별 숫자의 합을 계산할 때 DP를 효율적으로 사용할 수 있다.

 

예를 들어, n부터 m까지 순서에 있는 숫자를 다 더하는 알고리즘이 있을 경우 이 전에 0번째 숫자부터 5번째 숫자를 더했던 전적(?)이 있다면 이후 0번째 숫자부터 9번째 숫자를 더할 때 0~5까지의 합을 또 구할 필요가 없이 이전 결과를 활용할 수 있다. 이때 자료구조 하나를 선언해 결과를 저장하는 방식인 DP를 활용한다.

 

누적합은 DP보다 더 쉬울 수 있다! 

먼저 이 문제에서 문자열을 입력받았을 때, 문자열을 한 번 순환을 하는 것이다.

이때, 0번째 문자를 체크할 때 문자의 알파벳 대로 DP에 저장한다.

 

DP는 2차원 배열로 선언하며 행은 26, 열은 문자열 S 길이 만큼 선언하자.

0번째 문자가 예를 들어 'c' 라면 DP의 2번째 인덱스 ( 0번째 인덱스를 'a' 것이라고 가정하자) 의 0번째 인덱스에 1이라고 지정하자.

이는 즉, DP[2][0] = 1 이 된다.

 

이후 1번째 문자가 또 'c'라면 DP의 2번째 인덱스의 1번째 인덱스를 저장할 때

DP[2][1] = DP[2][0] + 1

를 한다. 왜? 

 

이전 0번째 까지의 문자열에서 'c'가 나타난 갯수인 DP[2][0] 에 1번째 문자 'c' 개수인 1을 더함으로써

DP[2][1] 의 값의 의미는 1번째 문자까지 'c'의 개수를 저장한다.

 

이렇게, 문자를 한번 순환하게 됨으로써 앞서 있었던 문자의 개수까지 계산을 하게 되는 것이다.

그러면 시간 복잡도는 O(N*M) -> O(N) 으로 변하게 되는 것이다 (이때 N은 문자열 S의 길이, M은 테스트케이스 수다.)

 

효율성이 극도로 높아진다!

 

그럼에도 불구하고 이 문제는 까다로울 수 있는 이유는, 

해당 문제를 누적합으로 풀 수 있다는 생각을 하지 못하면 시간초과의 미궁에 빠질 수 있기 때문에 어려운 문제라고 생각한다.

 

 

💻 정답 코드

#include <iostream>
#include <vector>
using namespace std;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string S; cin >> S;
	vector<int> dp[26];

	for (int i = 0; i < S.size(); ++i) {
		for (int j = 0; j < 26; ++j) {
			if (i == 0) {
				int num = S[i] - 'a';
				if (num == j) {
					dp[j].push_back(1);
				}
				else {
					dp[j].push_back(0);
				}
			}
			else {
				int num = S[i] - 'a';
				if (num == j) {
					dp[j].push_back(dp[j][i - 1] + 1);
				}
				else {
					dp[j].push_back(dp[j][i - 1]);
				}
			}
		}
	}
	int q, l, r;
	char alpha;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		cin >> alpha >> l >> r;
		int idx = alpha - 'a';
		if (l == 0) {
			cout << dp[idx][r] << "\n";
		}
		else {
			cout << dp[idx][r] - dp[idx][l - 1] << "\n";
		}
	}
	

	return 0;
}