[BOJ] 5525 IOIOI

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

5525번: IOIOI

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

문자열 분석 및 규칙 찾기

 

---------------------------------------------------풀이----------------------------------------------------

 

문자열 S를 처음부터 돌면서, IOI가 연속으로 반복되는 최장 길이들을 찾아 vector에 저장하였다.

예를 들어, OOIOIOIOIIOII 의 경우,

OOIOIOIOIIOII OOIOIOIOIIOII 이렇게 두 경우가 최장 길이이며, 각각 P3, P1이다.

그러므로 각각에 대해 P1이 포함되는 상황은 P3에서 3번, P1에서 1번으로 총 4번이다.

 

다시 보면,

Pn에 포함되는 Pn-1은 2번이고, Pn-2은 3번이다.

즉, Pk에 포함되는 Pn은 k-n+1번이다.

 

S를 처음부터 끝까지 돌면서 최장 길이를 찾는 과정은 O(N)이 걸리고

vector를 돌면서 k-n+1을 모두 더해주는 과정도 최대 O(N)이므로

O(N)에 해결이 가능하다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>
#include <deque>

using namespace std;

int N, M;
string S;
// 최장 Pn들을 구해 n들을 저장
vector<int> v;

// 최장 Pn을 찾아서 vector에 추가
void find_longest_IOs(){
    int len = 0;
    for(int i = 0; i < S.length()-2; i++){
        if(S[i] == 'I'){
            while(i < S.length()-2 && S[i+1] == 'O' && S[i+2] == 'I'){
                len++;
                i += 2;
            }
            if(len > 0){
                v.push_back(len);
                len = 0;
            }
        }
    }
}

// Pn = IOIOI...OI (N+1개의 I, N개의 O)
// string S 안에 Pn이 몇 군데 포함되어 있는가
int main(void){
    FASTIO;
    cin >> N >> M;
    cin >> S;
    find_longest_IOs();

    int answer = 0;
    // P3 = IOIOIOI => 여기에 포함된 P2 2개 P1 3개
    // P4 = IOIOIOIOI => 여기에 포함된 P3 2개 P2 3개 P1 4개
    // Pn => Pn-1:2개 Pn-2:3개 ...
    // Pk => Pn:k-n+1개
    for(int i = 0; i < v.size(); i++){
        // Pn이 포함된 개수 구하기
        if(v[i] >= N){
            answer += v[i]-N+1;
        }
    }
    cout << answer << "\n";

    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

한 번에 풀이가 보여서 다행이지, 안 보였으면 규칙을 찾는데 조금 걸렸을 것 같다.