백준 5525 IOIOI [자바]

03 May 2022 in Develop / Solving

baekjoon 5525 IOIOI

java

문제 분석

• I와 O가 띄어쓰기 없이 연속으로 들어옴.
• N에 따라, 연속된 문자열의 수를 체크
  • N이 1이면 IOI 의 수를 체크
  • N이 2이면 IOIOI 의 수를 체크
  • N이 3이면 IOIOIOI 의 수를 체크
  • …

N에 따라, 문자열 안에서 만족하는 문자열의 수를 뽑아낼 것.

입력조건

int_N
int_len
String_(IOIOIIIOI)

풀이과정

• 서브테스크로 나누어져 있는 것을 보고, 정성적으로 체크하면서 진행해서는 시간초과가 나는구나. 라고 생각하고 시작하였다.
• N에 대해, 체크하는 문자열의 길이는 최소 2N+1이다.

• IOI가 연속해서 나오는 것을 판단하면서, 지금 체크하고 있는 연속 길이가 2N+1 이상일 때 체크를 한다.

• 위처럼 진행하면, 문자열을 처음부터 끝까지 한번만 탐색하면서, 답을 추출할 수 있다.

핵심 파트

// 정답의 수를 담을 변수
int ans = 0;
// 현재 체크하는 곳이 IOI가 얼마나 연속되었는지를 체크
int conti = 0;
// idf는 식별자, 여기에 현재 위치의 문자 값을 넣어놓는다.
// O를 넣어놓으면, 처음에 O로 시작하든 I로 시작하든 다 처리할 수 있다.
char idf = 'O';

// 문자열을 한번 훑으면서 진행.
for(int i = 0; i < len; i++) {
    // 현재 위치 문자 받아옴. 
    char idfnow = arr.charAt(i);
    
    // 만약 저번 문자랑 다르면 연속수를 하나 증가.
    if(idf != idfnow) conti++;
    // 저번 문자랑 같으면, 초기화
    else {
        if(idfnow == 'O') conti = 0;
        else 			  conti = 1;
    }
    // 이번 문자를 넣음.
    idf = idfnow;
	
    // 연속수가 일정 조건을 만족할 때, 답을 증가.
    if (conti >= 2*N+1 && conti%2 != 0) ans++;
}

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BJ5525_IOIOI {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int len = Integer.parseInt(br.readLine());
		
		String arr = br.readLine();
		
		// N이 2N+1부터 세기 시작
		int ans = 0;
		int conti = 0;
		char idf = 'O';
		for(int i = 0; i < len; i++) {
			char idfnow = arr.charAt(i);
			if(idf != idfnow) conti++;
			else {
				if(idfnow == 'O') conti = 0;
				else 			  conti = 1;
			}
			idf = idfnow;
			
			if (conti >= 2*N+1 && conti%2 != 0) ans++;
		}
		System.out.println(ans);
	}
}