[백준 - 5525] IOIOI - C++

분류: 문자열 /

 

문제

문제 링크

문제 설명

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 P_N이라고 한다.

• P₁ IOI
• P₂ IOIOI
• P₃ IOIOIOI
• P_N IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 P_N이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력

S에 P_N이 몇 군데 포함되어 있는지 출력한다.

 

풀이

- 저장

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int N, M; 
    string s;
    cin >> N >> M >> s;
    
    int ans = 0;
    for(int i = 0; i < M-(N<<1); i++) {
        if(s[i] == 'O') continue;
        int cnt = 0;
        while(s[i+1] == 'O' && s[i+2] == 'I') {
            cnt++;
            i += 2;
            if(cnt == N){
                ans++;
                cnt--;
            } 
        }
    }
    cout << ans;
}

 

단순 문자열 매칭이면 KMP같은 문자열 매칭 알고리즘을 써야하지만 이 문제의 경우 2개의 문자로만 이루어 져있고 패턴을 찾는 문제다.

생각나는데로 문자열을 저장하고 `I`를 찾으면 `OI`의 수를 세 나가면 된다.

 

- 저장 하지 않고

#include <iostream>
using namespace std;

int N, M, ans, cnt;
char before, cur;
bool isCounting;

void calc(){
    if(cnt >= N) ans += cnt - N + 1;
    cnt = 0;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> M;
    while(M--) {
        cin >> cur;
        if(isCounting) {
            if(cur == 'I') {
                if(before == 'I') calc();
                else cnt++;
            } else if(before == 'O') {
                calc();
                isCounting = false;
            }
        } else if(cur == 'I') isCounting = true;
        before = cur;
    }
    calc();
    cout << ans;
}

문자열을 저장하지 않고 문자를 받아 바로 처리하여 문제를 해결 할 수 도 있다.

주의 할점은 `s`가 `IOI`로 끝날 경우 while문안에서 `calc`가 호출되지 않아 while문이 끝난 후 `calc`를 호출해줘야한다.