[BOJ] 백준: 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이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

풀이

저는 이 문제에 있어서 IOI 패턴이 반복되는 횟수를 저장하고 풀었더니 해결되었습니다.

하지만 다른 분들의 풀이를 확인해보니 주어진 N만큼 문자열들을 쪼개서 for문을 돌리면 50점밖에 받지 못한다고 하는데 제가 생각했을 때 substring에서 1번, 그 문자열을 패턴과 비교하는 곳에서 1번, 전체 문자열 배열들을 확인하는 곳에서 1번, 총 3번 for문이 돌기 때문에 50점 밖에 효율성을 받지 못했다고 생각합니다.

코드

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder("");

    static int N, M, patternCnt = 0;
    static char[] pattern;

    static void input() throws IOException{
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        pattern = br.readLine().toCharArray();
    }

    static void process(){
        int ans = 0;
        for(int i=1; i<pattern.length-1; i++){
            if(pattern[i-1] == 'I' && pattern[i] == 'O' && pattern[i+1] == 'I'){
                patternCnt+=1;
                if(patternCnt == N){
                    patternCnt-=1;
                    ans += 1;
                }
                i++;
            }else{
                patternCnt = 0;
            }
        }
        System.out.println(ans);
    }

    public static void main(String[] args) throws IOException{
        input();
        process();
    }
}

 

<출처>

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