백준 5525번 문제 바로가기

서브테스크가 있는 String 탐색 문제.

substr()을 이용한 해법

문자열 비교는 substr()을 사용하는 편이 가장 깔끔하게 해결할 수 있다. indexing에 비해서 직관적으로 코드를 작성할 수 있어 가독성이 높아진다. 다만 해당 string을 긁어와야하기 때문에 길이가 길어지면 그만큼 시간 소요가 많다는 단점이 있다.

#include <iostream>

using namespace std;

int main()
{
    int N, M;
    string S;
    cin >> N >> M >> S;
    
    // create Pn
    string Pn;
    for (int i=0; i<N; i++){
        Pn += "IO";
    }
    Pn += "I";
    
    // check Pn
    int count=0;
    for (int i=0; i<M-2*N+1; i++){
        if (S.substr(i,2*N+1) == Pn){
            count++;
        }
    }
    
    cout << count;

    return 0;
}

문자열을 그대로 사용하지 않고 count하는 해법

N과 M의 범위가 1,000,000까지 늘어나면 substr로는 시간 내에 해결이 불가해서 다른 방법들을 찾아 헤맸다. String을 한번만 긁고 더 이상 탐색하지 않는 방식을 고민했는데, 솔직히 다른 분들의 풀이를 참고해서 아이디어를 얻었다.ㅎㅎ

#include <iostream>

using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;
    
    string S;
    cin >> S;
    
    int count=0;
    
    for (int i=0; i<M; i++){
        int l=0;
        if (S[i]=='I'){
            while (S[i+1]=='O' && S[i+2]=='I'){
                l++;
                if (l==N){
                    l--;
                    count++;
                }
                i+=2; // OI가 한 단위
            }
            l=0;
        }
    }
    
    cout << count;

    return 0;
}