[BOJ/백준][Silver2] 5525 : IOIOI (C++)

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

5525번: IOIOI

 

 

[난이도] Silver2
[유형] 문자열

[풀이]
문자열의 최대 길이가 100만이므로 O(N^2)으로는 해결이 불가능합니다.
문자를 한번씩만 확인하는 O(N) 알고리즘으로 해결해야합니다.

일단 string 타입의 search 변수에 찾아야 하는 2*N+1 문자열을 만들어서 저장해놓습니다.
그 뒤, find 함수를 이용하여 입력문자열 s에서 start부터 탐색하여 search를 찾습니다.
만약 search가 없다면 그대로 루프를 종료합니다.
search가 있다면 search가 시작되는 인덱스 idx에서 search의 길이 2*N+1만큼 더한
idx에서 "OI"가 추가로 붙어있는지를 idx 2씩 증가시키며 확인해줍니다.
예를 들어 search가 IOIOI 일때, 어떤 IOIOI를 찾았다면, 그 뒤에 OI가 추가로 붙어있는만큼
search의 개수가 늘어나는 것입니다. (IOIOI(OIOI) <- OIOI가 뒤에 2개 더 붙어있으므로 search가 2개 더 늘어난다)

find를 통해 나온 search에서 몇개의 겹쳐진 search가 추가되는지를 찾아서 정답에 추가하고,
start를 다음 탐색해야하는 index로 옮겨주면서 루프를 진행해줍니다.

 

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
int N,M,ans;
string s,search;
int main(){
    cin >> N >> M >> s;
    for(int i=0;i<N;i++) search+="IO";
    search+="I";
    int start=0;
    while(start<s.size()){
        int idx=s.find(search,start);
        if(idx==string::npos) break;
        int k=1;
        for(start=idx+2*N+1;start<s.size()-1;start+=2){
            if(s[start]=='O'&&s[start+1]=='I') k++;
            else break;
        }
        ans+=k;
    }
    printf("%d",ans);
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/5525.cpp