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

 

 

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

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

 

---

 

문제 해결 과정

착안

입력으로 주어지는 문자열의 길이 $n$이 매우 길기 때문에 ($1 \leq n \leq 200000$) 동적계획법(dynamic programming)을 통해 각 알파벳 소문자 별로 인덱스 0부터 $i \space (i < n)$ 까지 해당 알파벳이 등장하는 횟수의 누적합을 먼저 계산하고, 구간이 주어질 때마다 누적합을 이용해 주어진 구간에서 알파벳이 등장하는 횟수를 계산하여 출력하고자 하였다.

 

구현

편의상 다음과 같은 조건에 따라 알파벳 등장 횟수에 대한 누적합을 저장할 배열 $Freq[i][j]$을 선언하여 활용하였다.

 

• 알파벳 소문자 a부터 z까지 각각 알파벳 순으로 0번째, $\cdots$, 25번째 알파벳이라 정한다.
• $i$번째 알파벳이 문자열의 0번째 인덱스부터 $j$번째 인덱스까지 등장하는 횟수를 $Freq[i][j]$에 저장.
• 보조 배열 DP[$j$]를 선언하여 동적계획법을 통한 누적합 계산에 활용.

 

이와 같이 누적합을 저장할 배열 $Freq[i][j]$을 계산하면, 구간 $[l, r]$ 내에 존재하는 $i$번째 알파벳의 수는

$$Freq[i][r] - Freq[i][l - 1]$$

이다(단 $l = 0$인 경우, $Freq[i][l - 1] = 0$).

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <string>

using namespace std;
int Freqs[26][200000];

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

	string Str;
	int Q;
	cin >> Str >> Q;

	int DP[26] = { 0, };
	for (int i = 0; i < (int)Str.size(); i++)
	{
		DP[Str[i] - 'a']++;
		for (int j = 0; j < 26; j++)
			Freqs[j][i] = DP[j];
	}
	
	while (Q--)
	{
		char word;
		int l, r;
		cin >> word >> l >> r;
		cout << Freqs[word - 'a'][r] - (l > 0 ? Freqs[word - 'a'][l - 1] : 0) << "\n";
	}

	return 0;
}

 

실행 결과