BOJ 5525 IOIOI

이 문제는 I,O로 구성된 문자열 중 IOI 가 몇개 포함되어 있는지 갯수를 구하는 문제이다. 처음 단순 부르트포스 방식으로 접근했다면 당연히 만점을 받지 못했을 것이다.  서브테스크 1의 경우 N<=100, M<=10,000이기 때문에 부르트 포스 방식으로 문제를 풀어도 O(NM) = 1,000,000 으로 통과 가능하다. 하지만 서브테스크 2의 경우 N<=1,000,000 M<=1,000,000 이기 때문에 통과할 수 없다.

 

이 문제를 푸는 방법은 크게 두가지이다. 

1. I의 위치(i)를 시작으로 i+1위치에 O, i+2위치에 I 가 있는지 확인해 나간다.

2. KMP 알고리즘을 이용하여 패턴 매칭을 활용하여 구한다.

 

간단한 방법은 1번을 활용한 풀이로 다행히 패턴이 규칙적이기 때문에 해결 가능한 방법이다. (이 문제 이외의 비슷한 문자열 탐색에는 사용할 수 없다)

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

int n, m;
string s;

void solution()
{
	int cnt = 0;

	for(int i = 0; i < m; i++)
	{
		if(s[i] == 'O')
		{
			continue;
		}
		
		int k = 0;//IOI 갯수
		while(s[i + 1] == 'O' && s[i + 2] == 'I')
		{
			k++;
			if(k == n)
			{
				cnt++;
				k--; // 오른쪽으로 +2만큼 이동했을때 k값 유지
			}
			i += 2;
		}
	}
	cout << cnt;
}

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

	cin >> n >> m >> s;
	solution();
}

 

다음은 KMP 알고리즘을 활용한 풀이이다. 자세한 알고리즘 설명은 여기를 확인하면 된다.

알고리즘 - KMP

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int n, m;
string s;

vector<int> getSkipTable(string pattern)
{
	int p = pattern.size();
	vector<int> skipTable(p, 0);

	int begin = 1, matched = 0; // matched는 몇개가 맞는지 length를 나타낸다.

	while(begin + matched < p)
	{
		if(pattern[matched] == pattern[begin + matched]) // matched는 접두부,begin+matched는 접미부를 나타낸다.
		{ 
			matched++;
			skipTable[begin + matched - 1] = matched;
		}
		else
		{
			if(matched == 0)
			{
				begin++;
			}
			else
			{
				// KMP 문자열 탐색 알고리즘 과 동일하게 불일치 발생 시
				// 매칭을 진행하면서 구했던 접두 접미사 길이 만큼 탐색을 건너뛸 수 있다
				begin += matched - skipTable[matched - 1];
				matched = skipTable[matched - 1];
			}
		}
	}
	return skipTable;
}


vector<int> kmpSearch()
{
	string pattern;
	vector<int> ret;
	vector<int> skip_table;

	for(int i = 0; i < 2 * n + 1; i++)
	{
		if(i % 2 == 0)
		{
			pattern.push_back('I');
		}
		else
		{
			pattern.push_back('O');
		}
	}

	int originLength = s.size(), patternLength = pattern.size();
	int begin = 0, matched = 0;

	skip_table = getSkipTable(pattern);

	while(begin <= originLength - patternLength)
	{
		if(matched < patternLength && s[begin + matched] == pattern[matched])
		{
			matched++;

			if(matched == patternLength)
			{
				ret.push_back(begin);
			}
		}
		else
		{
			if(matched == 0)
			{
				begin++;
			}
			else
			{
				begin += matched - skip_table[matched - 1];
				matched = skip_table[matched - 1];
			}
		}
	}
	return ret;
}

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

	cin >> n >> m >> s;
	vector<int> result;

	result = kmpSearch();

	cout << result.size();
}