[백준 5525] IOIOI

문제

---

접근

이 문제는 문자열 S 안에서 특정 패턴 Pn이 몇 번 등장하는지 확인하는 문제입니다.

처음엔 입력 값을 제대로 확인하지 않고 서브 태스크1에 있는 것을 보고 

1. i번째에서 i+3까지 자르고 i를 1개씩 올려가면서

2. Substring한 문자열이 Pn과 같은지 확인하였습니다.

이 경우 N이 매우 커졌을 경우에 2N+1 크기의 문자열을 M 번 확인해야하는 큰 연산이 걸려 매우 큰 시간복잡도가 나오게 됩니다.

그렇기 때문에 다른 방법을 사용하여야겠다고 생각하였습니다.

- 슬라이딩 윈도우 
고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘

슬라이딩 윈도우를 사용하여 Pn 문자열에서는 공통된 pattern이 존재하기 때문에 'IOI'를 고정 윈도우로 지정하여 윈도 내에 있는 데이터가 동일한지 확인하는 과정을 거쳐 결국 M * 3 의 연산을 진행해 1억 보다 작은 값을 갖게 되어 제한 시간 1초를 넘지 않게 됩니다.

로직

현재 위치에서 만약 IOI패턴이 발견되면 시작 위치를 2칸 앞으로 위치 시키고

발견되지 않으면 위치를 1칸만 앞으로 이동시켜 다시 IOI 패턴을 다시 확인합니다.

이러면 패턴이 연속적으로 등장하는 경우도 확인할 수 있습니다.

최종적으로 문자열에서 Pn이 몇 개 등장하는지 확인하는 로직은

IOI 패턴의 개수를 세어 oCount를 늘리고 또 이 과정에서 N에 도달했을 때마다 최종 카운트를 증가시키고 다시 oCount를 1 감소 시켜서 센 것에 대해서는 다시 처리하지 않도록 하였습니다. (여기서 oCount는 'IOI' 패턴 등장 개수입니다. 해당 패턴마다 N개의 O를 갖고 있기 떄문입니다.)

N에 도달하지 못한 경우엔 다시 초기화 하여 다시 oCount를 계산하도록 하였습니다.

예시

<입력>
2
13
OOIOIOIOIIOII

시간복잡도

O(M)

코드

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

public class Main {
    static int N;
    static int M;
    static int count;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        String S = br.readLine();
        count = 0;
        int start = 0;
        int oCount = 0;
        while (start < M-2) {
            if (S.substring(start, start + 3).equals("IOI")) {
                start += 2;
                oCount += 1;
                if (oCount == N) {
                    count += 1;
                    oCount -= 1;
                }
            } else {
                start += 1;
                oCount = 0;
            }
        }
        System.out.println(count);
    }
}