백준 5525: IOIOI

문제 요약

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이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

문제 분류

• 문자열

문제 풀이

50점을 맞기는 쉽다. 목표는 100점! 시간복잡도 O(n)에 해결하면 될 것 같다!
그를 위해 고민한 결과 슬라이딩 윈도우 엇비슷하게 구현하였다. 우선 find를 통해 문자열을 찾았는지의 여부를 저장한다. 문자열을 찾았을 때와 찾지 않았을 때의 메커니즘이 다르기 때문이다.

우선 순차적으로 'I'를 찾는다. 'I'를 찾았다면 for문을 이용하여 n에 대한 문자열 P를 찾는다. 그리고 find를 true로 설정한다.

문자열 P를 찾았다면, 그 뒤의 문자 2개가 OI로 이어지는 지 확인한다. 이어지면 문자열 P를 찾은 것이고, 그렇지 않으면 find를 false로 하고 그 위치에서부터 다시 문자열 P를 찾으면 된다.

다른 풀이를 찾아보니 KMP 알고리즘을 사용한 풀이가 많던데, KMP 알고리즘에 대해서도 공부해보아야겠다.

풀이 코드

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());
        int cnt = 0;
        String s = br.readLine();

        boolean find = false;
        int j = 0;
        for(int i = 0; i < m - 2 * n;) {
            if(find) {
                int interval = n * 2 + 1;
                if(i + interval + 1 >= m) break;
                if(s.charAt(i + interval) == 'O') {
                    if(s.charAt(i + interval + 1) == 'I') {
                        cnt++;
                        i+=2;
                    }
                    else {
                        i += interval;
                        find = false;
                    }
                }
                else {
                    i += interval;
                    find = false;
                }
            }
            else {
                if(s.charAt(i) == 'O') {
                    i++;
                    continue;
                }
                for(j = 0; j < n; j++) {
                    if(s.charAt(i + j*2 + 1) == 'I') break;
                    if(s.charAt(i + j*2 + 2) == 'O') break;
                }
                if(j == n) {
                    cnt++;
                    find = true;
                }
                else i++;
            }
        }

        bw.write(cnt+"");
        bw.flush();
        bw.close();
        br.close();
    }
}