[백준 5525] IOIOI (C++)

이 문제는 단순히 $P_N$을 구한 뒤, i번째 이후의 부분 문자열의 시작이 $P_N$인지 확인하면 정답이야 구할 수 있겠지만, 시간 복잡도가 $O(NM)$이므로 TLE가 발생한다.

해서, 우리는 다른 풀이를 생각해야한다. 처음에는 KMP를 생각했으나, 해당 알고리즘에 익숙치않아 구현에 실패했다. 하여, 다른 알고리즘으로 접근하기로 했다.

1
13
OOIOIOIOIIOII

위와 같은 입력이 주어졌을 때, $P_1$은 IOI로, 총 4군데에 포함이 되어있다.

• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII

2
13
OOIOIOIOIIOII

다음으로 위와 같은 입력이 주어졌을 때, $P_2$는 IOIOI로, 총 4군데에 포함이 되어있다.

• OOIOIOIOIIOII
• OOIOIOIOIIOII

그렇다면, 두 개의 포인터로 $P_k$의 시작과 끝 인덱스를 가리키도록해보자.

이 때, 0의 갯수인 $k$는 문자열 $P_k$의 길이를 2로 나눈 몫이 되므로 손쉽게 구해줄 수 있다. 그렇다면, $k \ge n$이라면, 우리는 $P_k$가 $P_N$을 포함한다는 것을 알 수 있다. 따라서, 이 경우 cnt를 증가시키면 된다.

그렇다면 투포인터로 $P_k$를 어떻게 표현할 수 있을까?

초기에는 i = 0으로 두고, s[i] == 'I'를 만족할 때 까지, i를 증가시킨다.

그리고, j = i + 1두고 아래의 과정을 반복하면 된다.

• s[j] == 'O' && s[j + 1] == 'I'가 참이면, j를 1 증가시키고 k >= n이면 cnt를 1 증가시킨다.
• s[j] == 'O' && s[j + 1] == 'I'가 거짓이면, i = j로 두고 s[i] == 'I'가 될 때까지 i를 증가시킨 뒤에, j = i로 설정한다.
• 마지막으로, j를 매번 1씩 증가시킨다.

이를 코드로 옮기면 다음과 같을 것이다.

for (j = i + 1; j < m - 1; j++) {
	if (s[j] == 'O' && s[j + 1] == 'I') {
		if ((++j + 1 - i) / 2 >= n) cnt++;
	} else {
		for (i = j; i < m && s[i] != 'I'; i++);
		j = i;
	}
}

마지막에 j를 1 증가시키기 전이니 j는 $P_k$의 마지막에서 두번째 문자를 가리키고 있기 때문에 위처럼 코드가 작성되는 것이니 주의하자.

이를 바탕으로 전체 코드를 작성해보자.

#include <bits/stdc++.h>
using namespace std;

int n, m, cnt;
string s;

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

	cin >> n >> m >> s;
	int i = 0, j;
	for (; i < m && s[i] != 'I'; i++);
	for (j = i + 1; j < m - 1; j++) {
		if (s[j] == 'O' && s[j + 1] == 'I') {
			if ((++j + 1 - i) / 2 >= n) cnt++;
		} else {
			for (i = j; i < m && s[i] != 'I'; i++);
			j = i;
		}
	}
	cout << cnt;
}