[백준] 5525번_IOIOI(Java)

문제 풀이

백준의 5525번 문제입니다. 문제 출처

(1) 문제 파악

(2) 문제 풀이 방법 생각하기

문자열 속에서 특정 문자열을 찾는 것입니다. 여기서 포인트는 OI가 반복된다는 것인데요!

OI가 연속으로 반복되는 횟수를 찾고 맨 앞이 I이면 count를 증가해주고, 시작 인덱스를 2 증가시키면 됩니다! 만약 OI가 연속되지 않을 경우에는 시작 인덱스를 1만 증가시켜서 다시 동작을 반복하면 됩니다.

(3) 시간 복잡도 확인

시간 제한은 1초 입니다. 즉, 대략 1억번 연산 안에 문제를 해결해야 합니다.

\[1 <= N <= 1,000,000\] \[2N+1 <= M <= 1,000,000\]

M의 최대 길이는 1,000,000이므로 처음부터 끝까지 인덱스를 돌며 연산을 해도 문제를 해결할 수 있습니다.

(4) 구현

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int stringLength = Integer.parseInt(br.readLine());
        String str = br.readLine();

        int count = 0;
        int answer = 0;

        for(int i=1; i<stringLength-1;) {
            if(str.charAt(i) == 'O' && str.charAt(i+1) == 'I') {
                count++;
                if(count == N) {
                    if(str.charAt(i-(count*2-1)) == 'I') answer++;
                    count--; // count를 하나 빼주는 이유는 다음 연산에서 2칸 이동 후 OI를 찾기 때문입니다.
                }
                i += 2;
            } else {
                count = 0;
                i++;
            }
        }

        System.out.println(answer);
        br.close();
    }
}