[백준] IOIOI in Java

📍 문제

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

 

I + OI이 n번 반복되는 문자열의 수를 찾으면 된다

이때 주의할 점은 IOI을 찾을 때 IOIOI 은 1개가 아니라 IOIOI IOIOI 해서 2개이다

 

📍 코드 설명

처음에 나는 i 이면 매번 뒤에 검사를 시작한다고 생각했는데 이러면 안된다.

 

시간초과가 나지 않기 위해선 최대한 내가 센 ioi를 기억하고 다시 활용해야 한다

그렇다고 막 dp문제처럼 풀어야하는건 아니고 그냥 내가 센걸 이용해야만 시간초과가 나지 않는다는 것만 기억하면 된다.

 

1. i이면 검사를 시작

2. oi이 몇번있는지 카운트

3. 내가 원하는 개수만큼 잇다

4. answer + 1 추가

5. 만약 oi이 아니다 -> 다시 1번 부터 시작

 

이런 문자열 가지고 노는 문제에서 가장 주의할 점은 Index 문제이다 꼮꼬꼮꼮꼮 경계값들 테스트해보고 

특히 while문 돌 때 절대 안나갈 것 같아도 내 뇌를 믿지말고 명시적으로 앞에 넣어주는 게 좋다

 

📍 코드

✔️ 코드

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 sLength = Integer.parseInt(br.readLine());
		char[] sArr = br.readLine().toCharArray();
	
		int answer = 0;
		for(int i = 0; i < sArr.length - 2; i++) {
			int ioiCnt = 0;
			if(sArr[i] == 'O') {
				continue;
			} else {
				while(i + 2 < sArr.length && sArr[i + 1] == 'O' && sArr[i + 2] == 'I') {
					ioiCnt++;
					if(ioiCnt == n) {
						ioiCnt--;
						answer++;
					}
					i+=2;
				}
			}
		}

		System.out.println(answer);		
	}
}

 

📍 틀린이유

처음에는 dp + 재귀로 풀었는데 시간초과가 자꾸 났다

재귀까지는 좀 주접이었음..머쓱ㅠ

문자열을 좀 더 많이 풀어봐야할듯

 

📍 기억할 것

인덱스 주의해!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!