P5525. IOIOI

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

5525번: IOIOI

설명

50점 풀이

첫번째 풀이는 부분 문자열(P)를 만들고, I와 O로만 이루어진 문자열(S)와 비교하였다. 

이 경우에 제한 조건에 걸려서(시간초과로 예상) 50점 풀이에 그쳤다. 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static String S;
    static String P ="";
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        S = br.readLine();

        for (int i = 0; i < N; i++) {
            P += "IO";
        }
        P += "I";

        for (int i = 0; i <= M - P.length(); i++) {
            String temp = "";
            for (int j = i; j < i + P.length(); j++) {
                temp += S.charAt(j);
                if (S.charAt(j) != P.charAt(j - i)) {
                    break;
                }
            }
            if (temp.equals(P)) {
                count += 1;
            }
        }
        sb.append(count);
        System.out.println(sb);
    }
}

100점 풀이

최소 P1인 IOI는 반복한다.

따라서 IOI 조건을 찾는 if문이 true라면, 문자를 2개 넘어서 다시 I를 찾는다.(i = i+2)

 

IOIOI... 로 n의 값이 커져 작은 IOI가 반복되어, 하나의 조건으로 문제를 풀 수 있다. 

 

count의 값과 n의 값이 같으면 결과를 나타내는 result 값을 1 증가한다.

 

코드

100점 풀이

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static char S[];
    static int count;
    static int result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        S = br.readLine().toCharArray();

        count = 0;
        result = 0;

        for (int i = 1; i < M - 1; i++) {
            if (S[i - 1] == 'I' && S[i] == 'O' && S[i + 1] == 'I') {
                count++;
                if (count == N) {
                    count -= 1;
                    result++;
                }
                i++;
            } else {
                count = 0;
            }
        }
        sb.append(result);
        System.out.println(sb);
    }
}

 

Reference

https://velog.io/@lifeisbeautiful/Java-%EB%B0%B1%EC%A4%80-5525%EB%B2%88-IOIOI-with-%EC%9E%90%EB%B0%94