[1] [Class 3] - 백준 5525 IOIOI

www.acmicpc.net/problem/5525

5525번: IOIOI

 

문자열 내에 특정 단어가 몇번 반복되냐를 계산하는 것이 목적인 문제입니다. 

 

제가 푼 방식은 이렇습니다.

찾아야 하는 단어가 I와 O의 반복이여서

한번 패턴이 매칭이 되면, 그 다음 앞의 2개만 더 IO면 되기 때문에

매칭에 성공할 시, 매칭된 단어의 갯수를 2를 줄이고 현재 위치에서 계속 판단하는 식으로 해서

시간 복잡도는 O(n) 으로 구성하였습니다. 

 

// 문자열 비교

#include <bits/stdc++.h>

using namespace std;

int main(){
  ios_base :: sync_with_stdio(false); 
  cin.tie(NULL);

  int N, L;
  string a;

  cin >> N >> L >> a;

  int count = 0;
  int curIdx = 0;
  int curMatch = 0;

  while(curIdx < a.size()){
    bool shouldBeI = (curMatch % 2) == 0;
    if(shouldBeI && a[curIdx] == 'I' || !shouldBeI && a[curIdx] == 'O'){
      curMatch += 1;
    }
    else if(!shouldBeI && a[curIdx] == 'I'){
      curMatch = 1;
    }
    else {
      curMatch = 0;
    }

    if(curMatch == N * 2 + 1){
      count += 1;
      curMatch -= 2;
    }

    curIdx += 1;
  }

  cout << count;
  return 0;
}