[백준/C++] 5525 IOIOI (S1)

유형	난이도	완료일	링크	특이사항
문자열	실버1	23/03/29	https://www.acmicpc.net/problem/5525

 

서브태스크 50점 코드

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

bool check = true;
int cnt = 0;

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

	
	for(int i = 0; i <= m-(2*n+1); i++)
	{
		check = true;
		
		for(int j = i; j<i+2*n+1; j++)
		{
			if((j-i+1)%2==1 && ioi[j]=='O')
			{
				check = false;		
				break;
			}
			else if((j-i+1)%2==0 && ioi[j]=='I')
			{
				check = false;
				break;
			}
		}
		
		if(check)
		{
			cnt++;
		}
	}
	cout << cnt;
}

가장 단순한 방식으로 문자열을 돌면서 패턴(찾을 문자열)과 주어진 문자열 내에서 패턴의 길이만큼을 비교한다.

주어진 문자열 길이에 비례하게 반복문을 돌면서 패턴과 맞는지 패턴 내부에서 또 반복문을 돌기 때문에 시간복잡도 O(n^2)로 n이 100만까지 커지면 통과할 수 없다.

완전 통과 코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int cnt = 0;
int check[1000001];
vector<int> container;
string ioi;

int main(void)
{
	int n, m;
	cin >> n >> m ;
	
	cin >> ioi;
	
	container.emplace_back(0);
	
	if(ioi[1]=='O' && ioi[0]=='I' && ioi[2]=='I')
	{
		container[cnt]++;
		check[1] = 1;
	}
	
	for(int i=2; i<m; i++)
	{
		if(ioi[i] == 'O' && ioi[i-1]=='I' && ioi[i+1]=='I')
		{
			if(check[i-2] == 1)
			{
				container[cnt]++;
				check[i]=1;
			}

			else if(check[i-2]!='O')
			{
				container.emplace_back(1);
				cnt++;
				check[i]=1;
			}
		}
	}
	
	int ans=0;
	
	for(int i= 0; i<container.size(); i++)
	{
		if(container[i] >= n)
		{
			ans+= container[i]-n+1;
		}
	}
	cout << ans;
}

KMP알고리즘 등 문자열 찾기에 쓰이는 알고리즘들도 찾아보았으나, 이 문제는 그런 알고리즘들을 구현할 줄 모른다고 하더라도 문자열이 ’I’와 ‘O’의 반복으로만 나타나 더 쉽게 풀 방법이 있을 것 같았다.

문자열을 받고 그 길이+@ 만큼만(O(N)) 반복문을 돌면서 “IOI…” 패턴이 연속으로 몇 개나 나오는지 미리 세 둔다. 센 값은 벡터에 저장해두고 내가 찾는 패턴의 길이 이상 연속된 값만 계산하여 내 패턴이 몇 번 들어갈 수 있을지 알아낸다.

IOI 패턴이 끊기고 새로 등장하면 벡터에 새 요소를 추가해 1부터 다시 연속된 IOI가 등장할 때마다 값을 누적한다. IOIOIOOIOIOI 처럼 끊어진 후 다시 패턴이 등장하는 부분에서 새로 벡터 요소를 추가하는 것이다.

IOI패턴의 개수를 O의 개수로 잡았을 때, 내가 계산해둔 IOI연속 패턴의 O가 M개 있고 내가 찾는 IOI 패턴의 O가 N개라면 내가 찾는 패턴이 M-N+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;
    cin >> n >> m;

    string s;
    cin >> s;

    int ans = 0;
    for (int i = 0; i < m; i++)
    {
        int k = 0; // k는 IOI의 길이. IOI면 1 , IOIOI면 2
        // O가 나오면 pass
        if (s[i] == 'O')
            continue;
        // s[i] == 'I'일 때
        else
        {
            while (s[i + 1] == 'O' && s[i + 2] == 'I')
            {
                k++;
                if (k == n)
                {
                    k--; // 중복 카운트를 막기 위해 -1 해준다.
                    ans++;
                }
                i += 2; // O를 건너 뛴다.
            }
            k = 0;
        }
    }
    cout << ans;

    return 0;
}

직관적으로 “IOI”의 개수를 직접 카운트한다. IOI 만큼 k를 증가시키고 k가 n에 도달하면 정답 카운트를 늘린 후 k를 1 깎는다. 이는 “IOIOIOI…”처럼 연속으로 IOI가 등장할 때 k가 n에 여러번 도달할 수 있게 하기 위한 장치이다. i+=2로 반복문을 조절하며 검사하는 방식도 시간도 단축되고 좋은 것 같다.