[실버 1] 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로만 이루어져 있다.

서브태스크

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

예제 입력 1

1
13
OOIOIOIOIIOII

예제 출력 1

4

풀이

1. Pn구하기 : Pn은 IOI에 OI 가 n-1개 만큼 붙은 것이다.
2. S를 pn의 길이만큼씩 잘라서 Pn과 일치할 경우 answer를 증가시켜준다.

-> 시간 때문에 50점이 떴다.

const input = require('fs').readFileSync('ex.txt').toString().trim().split('\n');

let [N, M, S] = input;
let pn = 'IOI' + 'OI'.repeat(N - 1);
let idx = S.indexOf(pn);
let lastIdx = S.lastIndexOf(pn);
let answer = 0;

for (let i = idx; i <= lastIdx; i++) {
  if (S.slice(i, i + pn.length) === pn) answer++;
}

console.log(answer);

개선

1 IOI
2 IOIOI     -> IOI IOI  (IOI가 2번 반복)
3 IOIOIOI   -> IOI IOI IOI (IOI가 3번 반복)
-> 이를 확인하기 위해 i를 2만큼 증가시켜 다시 확인하는것.

1. IOI 패턴이 나타날 경우 패턴 갯수를 증가시켜준다.
2. 패턴 갯수가 N과 일치할 경우 answer를 증가시키고 패턴 갯수를 감소시킨다.(이미 센 패턴이므로 제거)
3. 패턴 갯수가 N과 일치하지 않을 경우 i를 2만큼 증가시켜 이어나오는 문자열에 IOI 패턴이 또 존재하는지 확인한다.
4. 패턴이 또 존재하는 경우 다시 패턴 갯수를 증가시키고, 다시 패턴 갯수가 N과 일치하는지 확인해준다.
5. IOI 패턴이 없는 경우 패턴 갯수를 0으로 초기화시키고 i를 1만큼 증가시킨다.

const input = require('fs').readFileSync('ex.txt').toString().trim().split('\n');

let [N, M, S] = input;
let answer = 0;
let pattern = 0;
let i = 0;

while (i < M - 2) {
  if (S.slice(i, i + 3) === 'IOI') {
    pattern++;
    if (pattern == N) {
      answer++;
      pattern--;
    }
    i += 2;
  } else {
    pattern = 0;
    i++;
  }
}

console.log(answer);