[BOJ] 5525 IOIOI

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

5525번: IOIOI

---

문제

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

• P1 IOI
• P2 IOIOI
• P3 IOIOIOI
• PN IOIOI...OI (O가 N개)

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

---

입력

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

---

출력

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

---

제한

• 1 ≤ N ≤ 1,000,000
• 2N+1 ≤ M ≤ 1,000,000
• S는 I와 O로만 이루어져 있다.

---

풀이

다른 좋은 풀이가 있을 것 같지만 나는 에드 훅으로 풀었다.

나는 이렇게 푸는 것을 매우 싫어하는데 난이도가 낮아서 그런지 그래도 풀긴 풀었다.

문자가 연속해서 온 경우, 그렇지 않은 경우를 나누어서 구현했다.

IOI의 개수를 세는 것은 (O의 개수 - N +1)로 셀 수 있다.

1. 문자가 연속해서 왔는지 확인한다.
2. 문자가 연속해서 왔다면 I인 경우 IOI의 개수를 세고, O인 경우는 IOI의 개수를 세고 1을 뺀다.
3. 2번을 문자열을 다 셀 때까지 반복한다.
4. 끝부분은 세지 못했기 때문에 끝처리를 해준다.

 

---

코드

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>
#include <set>

#define p(a, b) make_pair(a, b)
#define SWAP(a, b, type) do { \
    type temp; \
    temp = a;  \
    a = b;     \
    b = temp;  \
} while (0)
#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int N,M;

void input() {
    cin>>N>>M;
}

void init() {
}


void solution() {
    ll ans=0;
    string s; cin>>s;
    bool flag_I=false; // 전에 위치가 I이면 True, O이면 False
    int cnt=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='I'){
            if(flag_I){ // I가 연속해서 나타났을 경우
                if(cnt+1>N) ans+=cnt-N+1;
                cnt=0;
            }else flag_I=true;
        }else{
            if(!flag_I){ // O가 연속해서 나타났을 경우
                cnt--; // O를 기준으로 세고 있었기 때문에 1을 빼줘야 한다.
                if(cnt+1>N) ans+=cnt-N+1;
                cnt=0;
            }else{
                cnt++;
                flag_I=false;
            }
        }
    }
    
    // 끝처리를 반드시 해줘야 한다.
    if(s[s.size()-1]=='O') cnt--;
    if(cnt+1>N) ans+=cnt-N+1;
    
    
    cout<<ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}