[백준, 자바, 5525번] IOIOI

풀이

• 해당 문제를 처음 봤을 때는 
• substring으로 특정 문자열을 찾으면 되겠구나 했지만
• 이렇게 쉬운데 정답 비율이 낮다는 건, 무슨 의도가 있겠구나 싶었음
• 그래도 우선 시도해보고 그에 따라 변화를 주는 것이 좋을 것 같다고 판단하여
• 그대로 실행했지만 역시나... 50%까지만 정답
• 이후 어떻게 해볼까 고민하다가
• 단순히 I와O의 반복되는 길이를 찾고
• 해당 구간에서 N길이에 따른 문자열의 길이를 카운팅하면 되지 않을까하고
• 알고리즘을 작성한 결과 무난히 통과!

 

// 성공 코드

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        String s = br.readLine();
        System.out.println(findResult(M,N*2+1,s));
    }
    private static int findResult(int M, int ms_ln, String s) {
        int cnt = 0;
        int ln = 0;
        char[] check = {'I','O'};
        for (int i=0; i<M; i++) {
            if (check[ln%2]==s.charAt(i)) ln++;
            else {
                cnt+=cal(ms_ln, ln);
                ln=check[0]==s.charAt(i)?1:0;
            }
        }
        if (ln!=0) cnt+=cal(ms_ln, ln);
        return cnt;
    }

    private static int cal(int ms_ln, int ln) {
        return ln>=ms_ln?(ln-ms_ln)/2+1:0;
    }
}

 

// 50% 코드

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        String s = br.readLine();
        System.out.println(findResult(M,N*2+1,makeString(N),s));
    }
    private static String makeString(int N) {
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<N; i++) sb.append("IO");
        sb.append("I");
        return sb.toString();
    }

    private static int findResult(int M, int ms_ln, String ms, String s) {
        int cnt = 0;
        for (int i=0; i<=M-ms_ln; i++) {
            if (s.substring(i,i+ms_ln).equals(ms)) cnt++;
        }
        return cnt;
    }
}