문제

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가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000)

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

접근

P(n) 수열은 맨 앞의 I를 떼고 생각해보면 OI가 n번 반복된 수열과 같다. 그러므로 처음 나오는 I의 다음 문자열부터 시작해서 OI가 나오는 횟수를 세주고, n번째 OI가 나왔다면 결과값을 1 증가시켜주면 된다. 물론 IOIOIOI 같은 형태라면 P(2)이 두번 나오는 형태이므로, OI가 n번째 나왔을 때 결과값을 1 증가시켜준 뒤 OI가 n-1번 나왔다고 생각하고 문자열의 끝까지 이어가면 된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static String s;
	static int m;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		//입력
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(bf.readLine());
		m = Integer.parseInt(bf.readLine());
		s = bf.readLine();
		
		//최종 출력물
		int result = 0;
		
		// 처음 나오는 I를 찾기
		int tmp = Find_I(0);
		// 만약 I가 없다면 0을 출력하고 끝내기
		if(tmp == -1) {
			System.out.println(result);
			System.exit(0);
		}
		
		// 첫 I 다음 문자부터 시작
		int now = tmp+1;
		// OI를 셀 변수
		int count = 0;
		
		while(now < m-1) {
			// 현재 위치와 다음 위치 문자가 OI면 카운트 +1
			if(s.charAt(now) == 'O' && s.charAt(now+1) == 'I') {
				count++;
				// 카운트가 n이면 P(n)과 같은 형태가 됐다는 뜻
				if(count == n) {
					result++;
					count--;
				}
				now += 2;
			}
			else {
				// 현재 위치와 다음 위치 문자가 OI가 아니라면 현재 위치부터 처음 나오는 I를 검색
				count = 0;
				tmp = Find_I(now);
				if(tmp == -1) {
					System.out.println(result);
					System.exit(0);
				}
				// 첫 I 다음 문자부터 다시 시작
				now = tmp+1;
			}
		}
		
		System.out.println(result);
	}

	private static int Find_I(int i) {
		while(s.charAt(i) == 'O') {
			i++;
			if(i == m)
				return -1;
		}

		return i;
	}	
}