1.문제

2.코드

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

/**
 * Author : YoungSeo Jeon
 * Date : 2021-08-29
 * Description : 백준 5525
 */

public class Main{
	public static void main(String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		//ioi의 갯수
		int n = Integer.parseInt(br.readLine());
		StringBuilder io = new StringBuilder();

		//문자열 길이
		int len = Integer.parseInt(br.readLine());
		
		String str = br.readLine();
    //정답
		int count = 0;
    //패턴 반복 횟수
		int chk_count = 0;
		for(int i=0; i<len-1; i++) {
      //IOI패턴인지 확인
			if(str.charAt(i)== 'I' && str.charAt(i+1)=='O' && str.charAt(i+2)== 'I') {
        //맞으면 반복횟수++ n과 일치하면 count++ 한후 다음패턴 확인위해 반복횟수--
				chk_count++;
				if(chk_count == n) {
					chk_count--;
					count++;
				}
				i++;  //O는 검사할 필요가 없음
			}else {//패턴이깨지면 반복횟수 초기화
				chk_count = 0;
			}
		}
		//출력
		bw.write(count+"\n");
		
		bw.flush();
		bw.close();
		br.close();
	}
}

3.Review

처음에는 StringBuilder로 문자패턴을 확인해주었는데 50점이 나왔다.
시간을 줄이기 위해서는 O(N^2)인 시간복잡도를 줄여줄 필요가 있었다.

따라서 IOI만 확인하는 방법을 사용하였다.

IOI패턴이 등장하였을때 O는 검사하지 않고 다음에도 IOI가 반복되는지 체크 한다.

IOI패턴이 반복되면 반복횟수를 늘려주고 반복횟수가 IOI문제의 N에 만족하면 카운팅을 해준다.

이런 방법을 사용하면 시간복잡도가 O(N)으로 줄어든다.