[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의 방식으로는 시간 초과가 납니다.

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

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

 

$PR{F}_{\alpha ,i}:=$ $S_{[1,i]}$에서의 $\alpha$의 등장 횟수 라고 정의하면,

각 쿼리의 답은 $PR{F}_{\alpha ,R}-PR{F}_{\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;
	}
}