BOJ 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이 몇 군데 포함되어 있는지 출력한다.
  
  
• 제한
  1 ≤ N ≤ 1,000,000
  2N+1 ≤ M ≤ 1,000,000
  S는 I와 O로만 이루어져 있다.
  
  
• 서브태스크

  번호	배점	제한
  1	50	N ≤ 100, M ≤ 10 000
  2	50	추가적인 제약 조건이 없다

• 50점짜리 풀이

#include<iostream>
#include<vector>
using namespace std;
int N, M;
char c[1000001];
vector<char> s;
bool checked;
void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

int main()
{
	void fast_io();
	int cnt = 0;
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> c[i];
	}
	for (int i = 1; i <= 2 * N + 1; i++)
	{
		if (i % 2 != 0)
		{
			s.push_back('I');
		}
		else
		{
			s.push_back('O');
		}
	}
	int temp = 0;
	while (temp < M)
	{
		checked = true;
		for (int i = 0; i < s.size(); i++)
		{
			if (c[temp] != s[i])
			{
				checked = false;
			}
			temp++;
		}
		if (checked)
		{
			cnt++;
		}
		temp = temp - s.size() + 1;
	}
	cout << cnt;
}

'I' 는 홀수 번째 'O'는 짝수 번째에 들어가므로 벡터에 N입력 만큼 IOI세트를 만들어준 후 입력한 문자열과 비교 하는 과정을 거쳤다.
이 방법은 서브태스크 1까지만 만족한다 (시간 복잡도 O(N)안에 못들어감)

* 100점짜리 풀이

#include<iostream>
#include<vector>
using namespace std;
int N, M;
char c[1000001];
vector<char> s;
bool checked;
void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
}

int main()
{
	void fast_io();
	int cnt = 0;
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> c[i];
	}
	for (int i = 0; i < M; i++)
	{
		int IoI = 0;
		if (c[i] == 'O') continue;
		while (c[i + 1] == 'O' && c[i + 2] == 'I')
		{
			IoI++;
			if (IoI == N)
			{
				cnt++;
				IoI--;
			}
			i += 2; //건너뛰는 용도
		}
	}
	cout << cnt;
}

IOI의 갯수를 체크하는 것이기 때문에 I일때 반복문을 통해 다음 이어지는 2개가 OI가 나오는지 체크하면 된다. IOI의 갯수를 count해주고 N개가 나올때마다 정답 수를 1씩 올려주면 된다 (같아질 때 1을 빼줘서 중복 count를 막아준다)