[BOJ/백준 5525][C++] IOIOI

문제

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

 

문제 내용

Pn은 (n+1)개의 I와 n개의 O가 번갈아 나오는 문자열을 의미한다.

이 문제는, 입력받은 문자열 S에 Pn이 몇 군데에 포함되어 있는지를 확인하는 문제이다.

 

문제 풀이

이 문제를 맨 처음에는 find()함수를 여러 번 써서 풀었는데, 이렇게 하면 50점만 받을 수 있었다.

그렇기 때문에 시간을 좀 더 단축시킬 수 있는 방법이 필요했다.

밑의 코드에서, k는 IOI의 개수를 의미한다.
문자열을 한글자씩 읽어나가며 문제를 해결한다.

현재 읽는 문자가 I이고, 이어지는 문자열이 OI 일 경우에 k의 값을 증가시킨다.
k가 n과 같아지게 되면, 문자열에 Pn이 존재하는 것이므로 ans(결괏값)을 증가시키면 된다.

코드가 잘 이해 안 될 수도 있는데, 예제를 가지고 하나하나 따져보면 이해가 될 것이다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

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

	//입력
	int n, m; string str;
	cin >> n >> m >> str;

	//문제 해결
	int ans = 0;
	for (int i = 0; i < m; i++) {
		
		int k = 0; //IOI의 개수
		if (str[i] == 'O') continue;

		while (str[i + 1] == 'O' && str[i + 2] == 'I') {
			k++;

			if (k == n) {
				ans++;
				k--; //오른쪽으로 +2만큼 이동할텐데 이때 k값이 바뀌지 않게 하나 빼줌
			}
			i += 2; //인덱스 뛰어 넘기
		}
	}

	//결과 출력
	cout << ans << '\n';

}