[C++] IOIOI (5525번)

IOIOI

문제

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가 주어진다.

출력

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

---

문제풀이

처음에 KMP 알고리즘을 사용해야 하나? 라는 생각이 들었지만 아무래도 난이도가 높은 문제가 아니었기 때문에 다시 차근차근 생각해 봤다.

사용되는 문자열이 두 개밖에 없고, 제한사항을 보아 이건 리니어한 방법으로 풀어야 한다고 생각했다.

 

맨 처음 문자열 길이만큼의 배열을 만들어 준다.

첫 문자가 I일 경우 배열에 1을, O일 경우 0을 넣는다.

두 번째 문자부터는 반복문을 돌린다.

4가지 경우로 나눌 수 있다. 우리는 Pn을 만드는 것이 목적이다.

1. 이전 것이 O이고 지금 것이 I인 경우 -> 이전 것 배열의 값에 1을 더해 지금 것 배열 인덱스에 넣어준다.

2. 이전 것이 O이고 지금 것도 O인 경우 -> 지금 것 배열 인덱스에 0을 넣어준다.

3. 이전 것이 I이고 지금 것이 O인 경우 -> 이전 것 배열의 값에 1을 더해 지금 것 배열 인덱스에 넣어준다.

4. 이전 것이 I이고 지금 것도 I인 경우 -> 지금 것 배열 인덱스에 1을 넣어준다.

 

이렇게 하면 배열에 숫자들이 저장되는데 이 숫자들의 의미는 바로 IO가 올바르게 반복된 숫자이다.

즉 IOI 인경우 마지막 배열엔 3이 저장되고, IOIO인 경우 4가 저장되고, 이런 식이다.

그렇기 때문에 Pn의 값인 3 + 2*(n-1) 보다 크거나 같은 경우는 Pn을 만들 수 있다는 말이 된다.

 

마지막으로 반복문을 처음부터 다시 돌면서 3 + 2*(n-1) 보다 크거나 같고, I인 경우만 answer을 1씩 더해주면 된다.

#include <iostream>
#include <string>

using namespace std;

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

	int n, m;
	string s;
	cin >> n >> m >> s;
	int arr[s.size()];
	if(s[0] == 'I')
		arr[0] = 1;
	else
		arr[0] = 0;
	
	for(int i=1; i<s.size(); i++) {
		if(s[i] == 'I' && s[i-1] == 'O') {
			arr[i] = arr[i-1] + 1;
		}
		else if(s[i] == 'I') {
			arr[i] = 1;
		}
		else if(s[i] == 'O' && s[i-1] == 'I') {
			arr[i] = arr[i-1] + 1;
		}
		else {
			arr[i] = 0;
		}
	}
	
	int check = 3 + 2*(n-1);
	int answer = 0;
	for(int i=0; i<s.size(); i++) {
		if(check <= arr[i] && s[i] == 'I')
			answer++;
	}
	cout << answer;
	return 0;
}

 

나는 -1 만 확인하는 방식으로 했는데 -1, -2 번째 인덱스까지 확인하는 방법으로 풀이해도 된다. 그게 좀 더 빠른 듯?