[Java] 5525 IOIOI

문제

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.

P1 IOI
P2 IOIOI
P3 IOIOIOI
PN IOIOI...OI (O가 N개)
I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, 
S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력
첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력
S에 PN이 몇 군데 포함되어 있는지 출력한다.

문제 풀이

부분 점수가 있는 문제이다. 

번호배점제한

 

1	50	N ≤ 100, M ≤ 10 000.
2	50	추가적인 제약 조건이 없다.

처음에는 단순히 I가 나오는 위치부터 한 칸 씩 옆을 비교하면서 처리를 했다. 당연하게도 50점을 받았다.

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

public class N5525 {
    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 line = br.readLine();
        int result = 0;
        
        // 입력받은 n값에 따른 찾아야하는 p의 길이
        int pLength = n * 2 + 1;

        // line.length() - pLength + 1 인 이유는 i부터 끝까지의 길이가 pLength 보다 작다면 굳이 확인할 필요가 없기 때문이다.
        for(int i = 0; i < line.length() - pLength + 1; i++){
            // 첫 검사 문자가 I일 때 
            if(line.charAt(i) == 'I'){
                boolean flag = false;
                
                // pLength만큼 다음 문자를 확인한다.
                for(int j = i + 1; j < i + pLength; j++){
                    
                    // false라면 I를 검사
                    if(!flag){
                        if(line.charAt(j) == 'I'){
                            break;
                        }

                        flag = true;
                    }
                    // true라면 O를 검사
                    else{
                        if(line.charAt(j) == 'O')
                            break;

                        flag = false;
                    }
                    
                    // 마지막에 j가 i + pLength길이까지 검사를 한 상태라면 하나를 찾을 것이니
                    // 결과를 +1 해준다.
                    if(j == i + pLength - 1)
                        result++;
                }
            }
        }

        System.out.println(result);
    }
}

100점을 받으려면 시간을 단축해야한다.

생각해보면 반복되는 부분은 IOI가 아닌 OI이다. OI를 하나의 단어로 보고 검사해나가다가 n만큼 OI를 찾았을 때 그 앞자리에 I가 있는 지 확인해보면 된다. 그리고 I를 +2씩 점프하면서 검사하면 시간을 단축할 수 있다.

자바 코드

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

public class N5525 {
    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 line = br.readLine();
        int cnt = 0, ans = 0;

        // 1번째 자리부터 시작 OI 검사
        for(int i = 1; i < len - 1;) {
            // OI의 문자열 일 경우
            if(line.charAt(i) == 'O' && line.charAt(i+1) == 'I') {
                // 찾은 OI 개수를 카운트 + 1
                cnt++;  
                // 찾은 OI 개수가 n개가 됐을 때
                if(cnt == n) {
                    // 찾은 OI들의 맨 앞이 I일 경우 답을 하나 찾은 것.
                    if(line.charAt(i - (cnt * 2 - 1)) == 'I')
                        ans++;
                    
                    // 2칸 씩 점프하면서 찾을 것이기 때문에 OI가 하나 없어지는 셈 
                    // cnt를 -1 한다.
                    cnt--;
                }
                // 2칸씩 점프
                i += 2;
            }
            // OI가 아닐 경우에 cnt를 리셋하고 i는 한 칸만 이동
            else {
                cnt = 0;
                i++;
            }
        }
        System.out.println(ans);
    }
}