백준 5525번 IOIOI // C++

문제

 

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

• P1 IOI
• P2 IOIOI
• P3 IOIOIOI
• PN IOIOI...OI (O가 N개)

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

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000)

출력

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

 

---

 

풀이

 

처음엔 find 함수를 써서 해당 문자열이 몇 번 나오는지 세려고 했는데 시간 초과가 발생했다.

 

따라서 IOI가 연속해서 나오는 횟수를 각각 세주면서, 패턴에 맞게 나온다면 결과 값에 1씩 더해주었다.

 

---

 

코드

#include <iostream>
#include <string>

using namespace std;
int N, M;

int main() {
	cin >> N >> M;

	string input;
	int count = 0;
	int res = 0;

	cin >> input;
	
	for (int i = 1; i < input.length() - 1; i++) {
		if (input[i - 1] == 'I' && input[i] == 'O' && input[i + 1] == 'I') {
			while (input[i-1] == 'I' && input[i] == 'O' && input[i + 1] == 'I') {
				count++;
				if (count == N) {
					count--;
					res++;
				}
				i += 2;
			}
		}
		count = 0;
	}

	cout << res;

	return 0;
}