[Java] 백준 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가 주어진다.

출력

S에 PN이 몇 군데 포함되어 있는지 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• 2N+1 ≤ M ≤ 1,000,000
• S는 I와 O로만 이루어져 있다.

서브태스크

번호배점제한

1	50	N ≤ 100, M ≤ 10 000.
2	50	추가적인 제약 조건이 없다.

예제 입력 1

1
13
OOIOIOIOIIOII

예제 출력 1

4

• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII

예제 입력 2

2
13
OOIOIOIOIIOII

예제 출력 2

2

• OOIOIOIOIIOII
• OOIOIOIOIIOII

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader bf;
	private static StringTokenizer st;
	
	private static int N, M, cnt=0;
	private static char []S;
	private static int []val;
	
	public static void main(String[] args) throws NumberFormatException, IOException {

		bf=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(bf.readLine());
		M=Integer.parseInt(bf.readLine());
		S=new char[M];
		val=new int[M];
		S=bf.readLine().toCharArray();
		
		for(int i=1;i<M-1;i++) {
			if(S[i]=='O' && S[i+1]=='I') val[i+1]=val[i-1]+1;	// 'OI'가 나타낼 때마다 그 이전 문자의 val + 1을 저장합니다.
			if(val[i+1]>=N && S[i+1-2*N]=='I') cnt++;	// OI의 개수가 N개 이상이 되고, 시작점이 I이면 개수를 1만큼 증가시킵니다.
		}
		
		System.out.println(cnt);
	}

}

 

 

 

출처 : https://girawhale.tistory.com/11

[백준] 5525번: IOIOI - JAVA