[Algorithm] 백준 5525번 : IOIOI (C++)

문제 링크 : https://www.acmicpc.net/problem/5525

5525번: IOIOI

---

[문제]

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

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

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

[입력]

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

[출력]

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

[제한]

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

[서브태스크]

번호	배점	제한
1	50	N ≤ 100, M ≤ 10,000
2	50	추가적인 제약 조건이 없다.

[알고리즘 분류]

• 문자열

---

[해설]

이 문제에서 요구하는 것은 입력된 s라는 문자열에 대해 "N+1 개의 I와 N개의 O가 번갈아 반복되는 문자열이 몇 번 나오는가?" 이다.
따라서, 본인도 처음에는 substr(), find() 등을 사용해 문제를 해결해보려 했으나 서브태스크의 조건 1번 밖에 만족하지 못해 50점만을 받았다.
때문에, 제약 조건 없이 문제를 해결할 수 있는 빠른 계산 알고리즘이 필요했다.
문제를 해결하기 위해서 아래와 같은 로직을 사용했는데, 동작 방식은 다음과 같다.

• i 인덱스의 문자가 'I' 인지 확인하고, 맞다면 i+1 번과 i+2 번째 인덱스를 합쳐서 문자열이 IOI가 완성된다면 반복문을 실행한다.
• 반복문 (조건 : i+1 = O, i+2 = I) 내에서는 k=N이 될 때까지 인덱스를 뛰어넘으며 확인하고 목표하는 문자열을 찾는다.
• 반복문 내의 k--는 오른쪽으로 i+2 만큼 이동하면서 k값이 바뀌지 않도록 1을 빼주는 역할을 함 ( k값이 커지면 문자열의 개수 계산 과정에서 답이 맞지 않게됨 )
• 위의 과정을 반복하면서 주어진 s 문자열 내에서 N+1 개의 I와 N개의 O가 번갈아 반복되는 문자열이 몇 번 나오는지 계산한다.

[정답 코드]

#include<iostream>
using namespace std;
int N,M,cnt=0;
string s;

int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  cin >> N >> M >> s;
  for(int i=0;i<M;i++){
    int k=0;
    if(s[i]=='I'){
      while(s[i+1]=='O'&&s[i+2]=='I'){
        k++;
        if(k==N){
          k--;
          cnt++;
        }
        i+=2;
      }
    }
  }
  cout << cnt;
}

[결과]