백준 Silver 1 IOIOI

IOIOI (백준 Silver 1)

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

N 개가 주어질 때, PN = IOIOI…OI (O가 N개) 라 한다
주어지는 문자열 S 에서
PN의 개수를 구하는 문제

제출 코드

#include<iostream>
#include<string>

using namespace std;

int main()
{
	int n,m;
	cin >> n >> m;
	string str;
	cin >> str;

	string findStr = "I";
	for (int i = 0; i < n; i++)
		findStr += "OI";

	int result = 0;

	int fSize = findStr.size();
    auto sBegin = str.begin();

	for (int i = 0; i < m - fSize + 1; i++)
	{
		if (str[i] == 'I')
		{
			string temp(sBegin + i, sBegin + i + fSize);
			if (temp == findStr)
				result++;
		}
	}

	cout << result;
	return 0;
}

틀린 이유?

처음에는 이 코드가 시간초과(50점)이 발생한 이유를 알 수 없었다
겉보기에는 ‘반복문’을 한번만 도니
O(N) 이라 생각하였다

(혹시 몰라 투 포인터를 써봤지만 역시 틀렸다)

그런데 곰곰히 생각해보니
‘문자열’을 저런식으로 ‘생성’하는 것과
‘문자열을’ 비교 하는 것이 과연 O(1)일까?

• 저런 식의 String 생성 방법 과
  substr 은 모두 O(N)의 시간 복잡도를 지닌다
  (문자열의 ‘길이’를 재고 index 부터 거기까지 잘라야 하므로)
  

• 또한 문자열 == 비교와
  compare 역시 O(N)의 시간 복잡도를 지닌다
  (일일이 문자를 비교하며 확인해야 하므로)
  

따라서 사실상 저 코드는
O(N^2)였다…

최종 코드

#include<iostream>
#include<string>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	string str;
	cin >> str;

	int result = 0;
	int count = 0;

	for (int i = 1; i < m - 1; i++)
	{
		if (str[i - 1] == 'I' &&
			str[i] == 'O' &&
			str[i + 1] == 'I')
		{
			count++;
			if (count >= n)
				result++;
			i++;
		}
		else
		{
			count = 0;
		}
	}

	cout << result;
	return 0;
}

코드 해설

사실상 연속된 ‘IOI’ 패턴의 개수를 구한 후
그 연속된 패턴의 개수가 n을 넘어가게 되면 result++ 해주는 방식이다
(이 때, IOI가 존재한다면 i를 2번 더해줘야 한다)

그 외에는 연속되지 않게 되므로 count를 초기화

결과

좀 많이 해맸다
아무래도 ‘구현’ 자체는 간단하였으나
string에 대한 연산이 그렇게 가볍게 이뤄지지 않는다는 사실을
다시 깨닫고 갈 수 있는 문제였다