[Java] BOJ 5525 IOIOI

문제 

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

• 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이 몇 군데 포함되어 있는지 출력한다.

아이디어

• IOI 패턴이 몇개 있는지 확인하여 그 개수와 반복되는 문자열의 길이 개수가 같다면 결과값을 카운트해준다.
• 반복 범위는 1부터 M - 2까지 하는데, 그 이유는 i-1, i, i+1번째 값이 IOI인지 판단해야되기 때문이다. 

겪은 시행착오

• 처음에는 단순히 반복되는 문자열의 길이가 얼마인지 보고 직접 IOI패턴을 만들어줬다
• 그리고 기준 문자열을 IOI패턴 길이만큼 subString을 통해 잘라줘서 IOI패턴이랑 같은지 비교했다.
• 만약 같다면 카운트를 해주는 식으로 했는데 50점을 받았다...
• 알고보니 문자열을 직접 더해줘서 만드는 것과 문자열을 자르고 비교하는 것이 시간이 많이 걸려서 시간초과 때문에 50점인 것 같았다.
• 그래서 시간을 최대한으로 줄이는 방법으로 코드를 짜기 위해서 고민을 좀 많이 했다....

문자열을 다룰 때는 시간초과를 조심하자..!!

코드

import java.io.*;
import java.util.*;

public class BOJ5525 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 반복되는 문자열 길이
        int N = Integer.parseInt(br.readLine());
        // 문자열 길이
        int M = Integer.parseInt(br.readLine());
        // 비교할 기준 문자열
        String S = br.readLine();

        // IOI 개수 카운트
        int cnt = 0;
        // 결과값
        int result = 0;

        // i-1, i, i+1번째 값이 IOI인지 비교하기 위한 반복문
        for(int i = 1; i < M - 1; i++){
            // i - 1번째가 I고 i번째가 O, i + 1번째가 I라면
            if((S.charAt(i - 1) == 'I') && (S.charAt(i) == 'O') && (S.charAt(i + 1) == 'I')){
                // IOI 개수 카운트 + 1
                cnt = cnt + 1;
                // 다음 IOI 패턴을 확인하기 위해서 i값을 증가시킴
                // 원래는 i++ 되면서 IOI패턴에서 i-1, i, i+1번째가 OIO가 되므로
                // 한번 더 증가시켜 주는 것
                i = i + 1;

                // 만약 찾은 IOI패턴이 찾아야되는 IOI패턴 길이와 같다면
                if(cnt == N){
                    // 결과값 + 1하고
                    result = result + 1;
                    // IOI패턴 카운트 한개를 빼줌
                    cnt = cnt - 1;
                }
            }
            // 만약 i-1, i, i+1이 IOI패턴이 아니라면
            else{
                // IOI패턴 개수를 0으로 초기화 시킴
                cnt = 0;
            }
        }

        System.out.println(result);
    }
}