[BOJ] 5525 IOIOI - JAVA

1. 문제

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

---

2. 풀이

1.  입력받은 문자열을 char배열로 만든다. string의 charAt보다 배열 접근이 더 편해서 나는 주로 이 방식을 사용한다.

2.  S[0]부터 S[M-N*2-1]까지만 첫글자로 탐색하면 된다. 이후는 Pn을 만들 수 없다. N*2+1이 Pn의 길이이기 때문이다.

3.  만약 S[start]가 O라면 시작문자열이 될 수 없으므로 넘긴다.

4.  count = 0으로 두고, 연속된 IOI의 길이를 찾는다. 한 번에 start+1, start+2를 탐색하기 때문에 start를 2씩 늘려가면서 찾으면 된다.

5.  count가 N보다 같다면 Pn을 찾은 것이다. answer에 1을 추가한다. 

6.  count > N인 경우도 체크하는 이유는 슬라이딩 윈도우 알고리즘을 생각하면 쉽다. P(n+1)이면 시작 ~ Pn , 시작+2위치 ~ Pn이 존재한다. 

import java.io.*;

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

      int answer = 0;
      int end = M-N*2-1;
      for(int start = 0;start<=end;start++){
         if(S[start]=='O') continue;
         int count = 0;
         while(start+2<M && S[start+1]=='O' && S[start+2]=='I'){
            if(++count>=N) answer++;
            start += 2;
         }
      }

      System.out.println(answer);
   }
}

---

3. 결과

substring도 써보고, 재귀도 써봤지만? 계속 틀렸다 ^_^ 어느 부분인지 체크못한 곳이 있었던것 같은데 못찾고 새로운 방식으로 풀었다.