[백준] 5525: IOIOI JAVA

접근

알고리즘 분류에는 문자열만 있지만, 나는 투포인터로 접근했다. 다른 사람들의 풀이를 보니, 한 칸씩 이동하며 연속된 IOI들의 개수를 세고 그 값이 N과 같아지면 answer를 카운팅하는 방식이다. 내가 실버 문제를 너무 복잡하게 생각한 것 같다. 아무튼 내 풀이 방법은 다음과 같다. 

 

left와 right 포인터를 두고, 두 포인터의 거리가 2*n가 될 때까지 움직이며 조건을 확인한다. 기본적으로 left는 고정하고 right를 움직이는데, 한 칸 전의 문자와 현재 문자가 같다면 조건을 만족하지 않기 때문에 left 위치를 right로 확 옮겨준다. 

 

만약 길이가 2*n을 만족하는 경우에는 left, 즉 시작 위치가 I로 시작하는 게 맞는지 확인한다. 아니라면 한 칸을 이동시켜 준다. 만약 맞다면 Pn의 조건을 만족하는 경우가 되는 것이다. answer의 값을 1 늘려주고, 이미 left~right 사이의 문자들은 IOI...IOI 를 만족하는 상태이기 때문에 바로 다음 I의 위치에서 시작할 수 있도록 left에 2를 더해줬다. 

 

반례 모음은 이쪽 → https://www.acmicpc.net/board/view/88287

 

코드

package week8;

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

public class BJ5525 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        String input = br.readLine();

        int left = 0, right = 1, answer = 0;
        char pre, cur = input.charAt(left);

        while(right < m){
            pre = cur;
            cur = input.charAt(right);

            // 동일한 문자가 연속됨
            if(pre == cur) left = right;

            // n 조건을 만족하는 길이가 됨
            if(right - left == 2*n){
                if(input.charAt(left) == 'O'){
                    left++;
                }
                else {
                    answer++;
                    left += 2;
                }
            }

            right++;
        }

        System.out.println(answer);
    }
}