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

 

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000)

 

문제는 매우 간단하지만 어떻게 확인하느냐를 가지고 매우 고민했다.

처음에 I를 찾으면 내가 원하는 IOIOI 등등이 맞는지 확인하였으나 전체 배열을 돌면서 확인하기때문에 엄청난 횟수를 돌게 된다.

( for문만 돌게되면 충분히 가능한 시간이 될 수도 있으나 IOIOI가 되는지 확인하는 부분에서 시간이 더 소요될 수 있으므로 시간초과의 가능성이 있다. )

 

내가 한 방법은 다음과 같다.

1. I의 인덱스만 따로 모은다.

   IOIOI 인 경우 [0,2,4] 가 될것이다.

2. 배열의 1번째 부터 돌면서 전 값과 차이가 2인지 확인한다.

   위의 경우 전값과 차이가 2인 것은 2번이 된다.

3. n = 2 일 경우를 생각해보면 전 값과 차이가 2인 것이 2이상일때마다 IOIOI가 한번씩 추가된다.

   IOIOIOIOIOIOIOIOIOIOIOIOI 를 생각해보면 이해가 쉽다.

   처음에 0,2,4 일때 차이가 2인것이 2번 나오므로 answer가 +1 되고

   다음 것을 보면 그대로 이어가 cnt가 3이 되는데 이때도 answer는 +1이 된다.

   그리고 차이가 2가 나지 않으면 그대로 cnt를 0으로 초기화 해주었다.

 

전체 소스코드를 보면 더 이해가 쉬울 것이라 예상이 된다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws Exception{
		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());
		String[] str = br.readLine().split("");
		int[] hash = new int[m];
		int idxArr = 0;
		for(int i=0; i<m; ++i) {
			if(str[i].equals("I")) {
				hash[idxArr] = i;
				idxArr++;
			}
		}
		int cnt = 0;
		int answer = 0;
		for(int i=1; i<idxArr; ++i) {
			if(hash[i]-hash[i-1] == 2) {
				cnt++;
			}else {
				cnt = 0;
			}
			if(cnt >= n) {
				answer++;
			}
		}
		bw.write(""+answer+"\n");
		bw.close();
		br.close();
	}

}