BOJ 5525 - IOIOI

문제 링크

문제#

$N+1$개의 I와 $N$개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 $P_N$이라고 한다.

• $P_1$: IOI
• $P_2$: IOIOI
• $P_3$: IOIOIOI
• $P_N$: IOIOI...OI (O가 $N$개)

I와 O로만 이루어진 문자열 $S$와 정수 $N$이 주어졌을 때, $S$ 안에 $P_N$이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력#

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력#

$S$에 $P_N$이 몇 군데 포함되어 있는지 출력한다.

풀이#

P_N은 IOI가 연속해서 $N$번 이어진 패턴으로 볼 수 있다. 문자열을 왼쪽부터 보면서 IOI가 이어지는 길이를 세면, 긴 IOIOI... 구간 안에 들어 있는 패턴 개수를 한 번에 셀 수 있다.

중요한 점은 패턴이 겹칠 수 있다는 것이다. 코드에서는 IOI가 이어질 때마다 count를 늘리고, count >= N이 되는 모든 순간을 답으로 센다. 패턴이 끊기면 다음 위치에서 다시 시작하므로 전체 문자열을 선형으로 처리할 수 있다.

코드#

#include <iostream>
using namespace std;
 
void solve() {
	int n, m, count, answer = 0;
	string s;
 
	cin >> n >> m >> s;
	
	for (int i = 0; i < m; i++) {
		if (s[i] == 'I') {
			count = 0;
 
			while (i + 2 < m) {
 
				if (s[i + 1] == 'O' && s[i + 2] == 'I') {
					count++;
				}
				else {
					break;
				}					
 
				if (count >= n) 
					answer++;
 
				i += 2;
			}				
		}
	}
 
	cout << answer << '\n';
}
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	solve();
 
	return 0;
}

복잡도#

• 시간 복잡도: 문자열을 한 번 훑으며 패턴 길이를 갱신하므로 $O(M)$이다.
• 공간 복잡도: 추가 자료구조 없이 카운터만 사용하므로 $O(1)$이다.

마무리#

겹치는 IOI 패턴을 놓치지 않으려면 긴 교대 구간을 길이로 세는 편이 좋다. 이어진 횟수가 $N$ 이상이 되는 순간마다 하나의 P_N이 만들어진다.