백준 5525번 IOIOI 서브태스크 50점 (java)

String태그의 문제이다.

처음에 50점 맞은 풀이는 아래와 같다.

커서를 이용해서 커서를 단위로 substring으로 잘라서 검사했다.

근데 예제는 IOI를 기준으로 잘라서 단순해보이지만 만약 N이 많이 커진다면 겹치는 데이터를 다시 자르는 일이 발생

위처럼 굳이 검사하지 않아도 되는 부분을 다시 잘라서 보게된다.

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

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));

        int N = Integer.parseInt(br.readLine());

        String P = "";

        for (int i = 1; i <= 2 * N + 1; i++) {
            if (i % 2 == 0) P += "O";
            else P += "I";
        }

        int M = Integer.parseInt(br.readLine());
        String S = br.readLine();
        int cnt = 0;

        int l =0;
        int r = 2*N;

        while(r<=M-1){
          if(S.substring(l,r+1).equals(P)){
              cnt++;
              l+=2;
              r+=2;
          }else {
              l++;
              r++;
          }
        }

        bw.write(Integer.toString(cnt));
        bw.flush();
        bw.close();
        br.close();


    }

}

그래서 풀이를 고쳐야 한다.

최소 단위(IOI)를 세서 cnt에 누적한다. 만약에 cnt의 값이 내가 찾고자 하는 N과 일치한다면 cnt=cnt-1을 해준다. 이렇게 하면 굳이 앞 부분을 다시 자를 필요없이 내가 본 cnt의 개수 중에서 앞에 IOI하나를 빼고 다시 시작할 수 있다.

예를 들어 IOIOIOIOI이고 나는 N이 2인 IOIOI가 저기에 몇 개 들어가는지 알고 싶다.

IOIOIOIOI
굻은 글씨까지 도달하면 cnt=2 따라서 cnt==N이기 때문에 하나를 발견했으니 result(답)에+1을 해주고 cnt=cnt-1을 해준다 저기에서 나는 하나의 IOI를 빼준것이다 그러니

IOIOIOIOI
저기를 봤다 치고 cnt=1인 상태에서 다시 시작한다.

그래서 풀이는 아래와 같다.

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

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));
        
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        char[] S = br.readLine().toCharArray();
        
        int i=1;
        int cnt =0;
        int result =0;
        while(i<=M-2){
            if(S[i-1]=='I'&& S[i]=='O' && S[i+1]=='I'){
                cnt++;
                
                if(cnt==N){
                    cnt--;
                    result++;
                }
                i++;
            }else{
                cnt=0;
            }
        }
        
        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();

    }


}