취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 23921번 문제인 Kick_Start이다.
문제는 아래 링크를 확인하자.

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

주어진 문자열을 앞부터 차례대로 읽어나가면서, 지금의 문자를 읽었을 때 "START"문자열이 완성되었는지 확인하는 것은 어렵지 않다. 이 때, 이 "START"로 문자열이 완성될 경우의 수는 이 시점까지 완성된 "KICK"의 수와 같음을 관찰하자. 또한 "START"와 "KICK"의 마지막 문자가 서로 다르므로 두 문자열이 동시에 완성되는 경우는 없음을 관찰하자.

위의 관찰을 이용하면, 문자열을 앞부터 읽어나가면서 "START"가 등장할 때마다 지금까지 등장한 "KICK" 부분문자열의 개수를 더하는 것을 반복하는 것으로 문제를 해결할 수 있음을 알 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

int N;
string s;

void solve() {
	cin >> s; N = s.length();
	ll ans = 0, kcnt = 0;
	for (int i = 0; i < N; i++) {
		if (i > 3 && s.substr(i - 4, 5) == "START") ans += kcnt;
		else if (i > 2 && s.substr(i - 3, 4) == "KICK") kcnt++;
	}
	cout << ans << '\n';
}

int T;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;
	for (int t = 1; t <= T; t++) {
		cout << "Case #" << t << ": ";
		solve();
	}
}