백준 - 5525번 : IOIOI (C++)

풀이 방법 : 문자열 탐색(?)

이런 풀이를 뭐라 해야하는 지를 모르겠다. 일단 조건에 맞는 부분 문자열은 무조건 I로 시작해야한다.
0번 인덱스부터 문자열을 탐색해나가면서 I를 만날 경우 while문 안에 들어가서 계속 반복 돌려주면서 그 다음 문자가 O 그 다음문자가 I인지 알아내면서 Length를 늘려나간다. Length가 조건에 맞는 문자의 길이인 (N * 2 + 1)에 도달할 경우 카운트 증가 시켜준다.

만약 조건에 맞는 문자열일 경우 Length에서 2를 빼주고 그 다음 두 개의 문자열이 OI인지 검사하기만 하면 다음 부분 문자열을 찾아낼 수 있다.

또한 조건에 맞지 않는 문자열임이 밝혀졌을 경우 지금까지 검사한 인덱스의 문자로 시작한 부분 문자열은 무조건 조건에 맞지 않는 문자열이라는 것이므로 마지막으로 만난 I부터 다시 검사를 해주면 되니 반복자에 적절한 숫자를 더해주면 반복수를 현저하게 줄일 수 있다.

#include <iostream>

using namespace std;

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;

	string Str;
	cin >> Str;

	int SubStrLength = 2 * N  + 1;
	int Cnt = 0;

	bool Enable = false;

	for (int i = 0; i < M; ++i)
	{
		if (i + SubStrLength > M)
			break;

		if (Str[i] == 'I')
		{
			int Length = 1;
			
			while (true)
			{
				if (Length == SubStrLength)
				{
					i += 2;
					Length -= 2;
					++Cnt;
					continue;
				}

				if (Length % 2 == 1)
				{
					if (Str[i + Length] == 'O')
						++Length;

					else
					{
						i = i + Length - 1;
						break;
					}
				}

				else
				{
					if (Str[i + Length] == 'I')
						++Length;

					else
					{
						i = i + Length - 2;
						break;
					}
				}
			}
		}
	}

	cout << Cnt;
}

선형 자료구조를 순차적으로 탐색해야 할 때는 항상 이전 결과에 따라 스킵할 수 있는 구간이 있는지 없는지 고민해보고 문제풀이에 들어가자...