[백준] 5525번. IOIOI

틀린 풀이 (50점) -> 시간초과때문

이 문제는 거의 매 Idx 마다 Pn 인지 확인하는게 필요하다 생각되었다.

현재 idx 에서 Pn 임을 검증하는 것이

• 성공한 경우 -> idx + 2 위치부터 이어나간다
• 실패한 경우 -> idx + 1 위치부터 이어나간다.

따라서 매 idx 마다는 매번 최대 2 * n + 1 만큼의 비교가 일어나고 idx 는 대략 s.length() 길이인 M 만큼이 가능하다고 한다면

M x N 정도이게 된다 -> 몇백만.... 이니 이렇게 풀어도 될 것 같다는 생각이 들었다.

public class Main {

    private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private StringTokenizer st;


    public void run() throws IOException {
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        String s = br.readLine();
        int idx = 0;  int cnt = 0;

        while((2 * n + 1 + idx) <= m) {
            if(s.charAt(idx) != 'I') {
                idx++;
                continue;
            }
            if(checkPn(n, idx, s)) {
                idx += 2;
                cnt++;
            } else {
                idx += 1;
            }
        }

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

    // idx 부터 시작해서, s 에 Pn 이 존재하는 지 검증하는 로직
    private boolean checkPn(int n, int idx, String s){
        if(idx + (2 * n + 1) > s.length()) return false;  // 이거는 상위 계층에서 확인해 주는게 맞을 듯

        for(int i = 0 ; i < n; i++) {
            if(s.charAt(idx + 2 * i) != 'I') return false;
            if(s.charAt(idx + 2 *  i + 1) != 'O') return false;
        }

        if(s.charAt(idx + 2 * n) != 'I') return false;

        return true;
    }
    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.run();
    }
}

-> 하지만 이렇게 풀면 시간 초과로 인해 50 점 이라는 점수 밖에 받지 못한다.

그렇다면 아마... O(M) 을 원하는 것 같다.

중복돼서 확인하는 것을 원하지 않는 것 같다.

O(M) 으로 풀기

위의 방식은 IO 가 n 개 오는 것을 확인 한 후 마지막에 I 가 오는지를 확인하는 식으로 Pn 을 검증하는 것이었다.

그니까.. 이미 지나온 부분은 다시 확인하지 않는다.
그러면 이런 생각이 든다.

• Pn 이 나왔다면 바로 연속한 뒤의 두 글자만 확인해서 OI 이기만 해도, Pn 의 개수가 또 1 증가하네?
• Pn 이 도중에 실패했다면, 현재까지의 idx + 1 위치부터 처음부터 확인하면 되네?

이거를 좀 더 정리해서 생각 해 보면

• I 다음에 OI 가 N 개 반복되는지를 확인하는 식으로 Pn 의 존재를 검증 해 주자.
• 한 번 Pn 을 발견하면 -> 정답 개수 1 증가 시키고, -> 이 뒤에 OI 가 있는지만 확인 한다 -> 있으면 또 정답 개수를 1 올리면 된다. ( OI 의 연속 개수만을 세면 되는 것이다 )
• 한 번 Pn 이 실패 되면 -> 다음 idx 는 '지금까지의 index + 1 위치' 부터로 하면 된다.

이를 반복문을 통해서 검증하기 위해서는
i 와, 반복되는 OI 의 개수 k 를 잘 사용해야 한다.

for 문의 i 는 연속한 Pn 이 존재할 때, 가장 처음 등장하는 Pn 의 시작점 이라고 생각 해 주면 된다.
for 문을 통해서 i 를 업데이트 하는 것은, 중간에 Pn 이 아닌 경우 이다.

연속된 Pn 이라는 것은 n = 1 일 때 IOIOI 는 i =0 일 때, i = 2 일 때 , 총 두 개의 Pn 이 존재하는데, 이들 Pn 은 연속되어 존재한다. 보면 I 뒤에 OI가 1개 존재함을 발견 -> Pn 카운트 1증가 -> 오? 그런데 보닊, 이 바로 뒤에 또 OI 가 존재하면 Pn 을 1 증가 시키면 됨 -> ...

이걸 구현하면 되는 거임.

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

public class Main {

    private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private StringTokenizer st;


    public void run() throws IOException {
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        String s = br.readLine();

        int cnt = 0;
        for (int i = 0; i < m; i++) {
            if (s.charAt(i) == 'O') {
                continue;
            }
            int k = 0;

            // 현재 i 로부터 OI 를 확인해야 하니, 길이가 가능한지 확인 해 본다
            while (i < s.length() - 2 && s.charAt(i + 1) == 'O' && s.charAt(i + 2) == 'I') {
                k++;

                // OI 가 N 개 연속해 있는 경우
                if (k == n) {
                    cnt++;
                    k--;
                }
                i += 2;
            }
            // 연속해서 OI 가 N 개 나오는 것이 실패한 경우 , for 문을 통해 i 는 1 증가한다. 해당 위치부터 다시 처음부터 확인하면 된다.
        }

        System.out.println(cnt);
    }

    public static void main(String[] args) throws IOException {
        Main main = new Main();
        main.run();
    }
}