[Java] 백준 5525.IOIOI

➡️문제 링크

https://www.acmicpc.net/problem/5525

 

💡아이디어

배점도 나눠져 있고 범위 조건도 있어

분명 시간 초과 날 것 같은데

일단 이중 for문 돌려보고 다시 생각해보자

 

 

✏️문제 풀이

1. 완탐- 오답

Pn의 길이:  2*N+1

그래서 이중 for문을 돌려 순차 탐색으로 처음부터 2*N+1 씩 쪼개서 판단했다

N과 M의 1차 조건 내에서는 성공했지만, 조건이 사라지니 실패!

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());	// S의 길이
		String str = br.readLine();
		
		int result = 0;
		int length = 2*N+1;
		for(int i = 0; i <= M-length; i++) {
			String tmp = str.substring(i, i+length);

			boolean flag = true;
			for(int j = 0; j < length; j++) {
				if(j%2 == 0) {	// 짝수 -> I
					if(tmp.charAt(j) != 'I') {
						flag = false;
						break;
					}
				}else {
					if(tmp.charAt(j) != 'O') {
						flag = false;
						break;
					}
				}
			}
			if(flag) result++;
		}
		
		System.out.println(result);

	}

}

 

 

 

2. 문자열 비교  - 성공

문제를 다시 정리하면, 결국 "IOI"가 몇 번 등장하느냐!가 중요 포인트다

인덱스는 1부터 시작해서

i-1, i, i+1 이렇게 세 문자가 I, O, I 인지 확인한다

만약 아니라면, 연속되는 문자열이 아니기 때문에 count 는 초기화, 

맞다면

count 증가하면된다.

그러다 count가 N이라면

문제에서 구하고자 하는 Pn만큼 구해졌다는 거기 결과값을 + 하면 된다.

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());	// S의 길이
		char [] str = br.readLine().toCharArray();
		
		int count = 0;
		int result = 0;
		
		for(int i = 1; i < M-1; i++) {
			if(str[i-1] == 'I' && str[i] == 'O' &&str[i+1] == 'I') {
				count++;	// IOI인 경우
				
				if(count == N) {	// ioi 연속 세트가 N인 경우
					count--;
					result++;
				}
				i++;
			}else {
				count = 0;	// 연속 실패니 초기화
			}
		}

		System.out.println(result);

	}

}

 

 

 

 

 

역시 아이디어 떠올리는게 어렵다

부지런히 문제 풀어야겠다