문제

백준 5525번
https://www.acmicpc.net/problem/5525

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

---

생각하기

문자열의 겹치는 부분을 계산하면 되는 문제인데, 생각보다 까다롭고 많이 어려웠다.

동작

		int result = 0;
		int count = 0;

		for(int i=1; i < M - 1; i++) {
		if(s[i - 1] == 'I' && s[i] == 'O' && s[i + 1] == 'I') {
				count++;

				if(count == N) {
					count--;
					result++;
				}
                i++;
			}
			else {
				count = 0;
			}
		}

겹치는 부분을 고려해야한다.

IOIOI에서 IOI를 찾는다고 하면, 2개이기때문에, 이 부분의 구현이 중요하다.

최소 P1의 값이 IOI인 3의 길이 이므로, 이 3의 구간이 반복이라고 보면된다.
그렇기 때문에 IOI의 조건을 찾는 if문이 true일 경우,
2개의 문자를 뛰어넘고 다시 I를 찾아야해서 i++;를 한번 해준다.

이렇게 해주면 조건에 일치할 경우에는 i=i+2가 되어서 2개의 문자를 뛰어넘고
다시조건을 찾을 수 있게 해준다.

IOIOIOIO...식으로 n의 값이 커져서 얼마가되던 작은IOI의 반복임을 생각한다면, 하나의 조건으로도 문제를 풀 수 있음을 알게 된다.

일치하는 값인 count 와 N의 값이 같아지면 결과를 나타내는 result를 증가한다.

---

코드

import java.io.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		char s[] = br.readLine().toCharArray();

		int result = 0;
		int count = 0;

		for(int i=1; i < M - 1; i++) {
		if(s[i - 1] == 'I' && s[i] == 'O' && s[i + 1] == 'I') {
				count++;

				if(count == N) {
					count--;
					result++;
				}
                i++;
			}
			else {
				count = 0;
			}
		}

		System.out.println(result);

	} // End of main
} // End of class