[2022.04.17.] 인간-컴퓨터 상호작용

문제 정보

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

난이도: Silver I

분류: [누적합]

 

문제 요약

문자열 \( S \)에서 \( \alpha \)라는 알파벳이 \( [L, R] \) 구간 내에서 총 몇 번 등장하는지 묻는 문제입니다.

+ 쿼리 문제로, \( [L, R], \alpha \)가 바뀝니다.

 

서브태스크 1 (50점)

직접 \( [L, R] \) 구간을 돌리면서 \( \alpha \)의 등장 횟수를 세면 됩니다.

시간복잡도는 \( O(Q|S|) \)회입니다.

void Main(){
	string s; cin >> s;
	int q; cin >> q; while (q--){
		char ch; int l, r; cin >> ch >> l >> r;
		int ans = 0;
		for (int i = l; i <= r; i++){ ans += (s[i] == ch); }
		cout << ans << endl;
	}
}

 

서브태스크 1+2 (50+50점)

서브태스크 1의 방식으로는 시간 초과가 납니다.

하지만, 구간에서의 개수를 구하는 거니 누적합을 써주면 될 것 같은 느낌이 듭니다.

그러니, 각 알파벳별로 누적 등장 횟수를 저장해주면 누적합으로 풀 수 있는 문제가 됩니다.

 

\( PRF_{\alpha, i} := \) \( S_{[1, i]} \)에서의 \( \alpha \)의 등장 횟수 라고 정의하면,

각 쿼리의 답은 \( PRF_{\alpha, R} - PRF_{\alpha, L-1} \)이 됩니다.

 

시간복잡도는 \( O(|S| + Q) \)이고, 공간복잡도는 \( O(26 |S|) \)입니다.

int prf[26][200001];

void Main(){
	string s; cin >> s; int n = s.size(); s = " " + s;
	for (int i = 1; i <= n; i++){
		for (int j = 0; j < 26; j++){ prf[j][i] = prf[j][i-1]; }
		prf[ s[i]-'a' ][i] += 1;
	}
	int q; cin >> q; while (q--){
		char ch; int st, ed; cin >> ch >> st >> ed; ch -= 'a'; st += 1; ed += 1;
		cout << prf[ch][ed] - prf[ch][st-1] << endl;
	}
}