백준 5525번: IOIOI

 

50점 짜리 풀이:

1. 입력받은 문자열을 target문자열 크기만큼 substring한다.
2. 자른 문자열이 target문자열인지 확인한다.
3. 위 과정을 반복하며 개수를 카운트한다

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		// 입력
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		String inputIOI = br.readLine();

		// 찾아야하는 문자열 만들기
		StringBuilder sb = new StringBuilder();
		sb.append("I");
		for (int i = 0; i < n; i++) {
			sb.append("OI");
		}
		String targetIOI = sb.toString();

		// 문자열 찾기
		int cnt = 0;
		int targetSize = targetIOI.length();
		for (int i = 0; i <= m - targetSize; i++) {
			// 입력 문자열을 i ~ i+targetSize 만큼 잘라서 target 문자열인지 확인
			String substr = inputIOI.substring(i, i + targetSize);
 
			if (substr.equals(targetIOI)) {
				cnt++; // target이면 cnt 증가
				i++; // IOI패턴 특성을 이용하여, 문자열 인덱스를 2씩 증가시켜 탐색 효율 올림
			}
		}
		// 출력
		bw.write(String.valueOf(cnt));
		bw.flush();
		bw.close();
		br.close();
	}
}

시간초과로 50점을 받은 듯 하다.

 

100점 짜리 풀이:

 

1. 패턴 매칭: while 루프를 통해 문자열 s를 순차적으로 검사
2. 패턴 검증: 주어진 위치에서 PN 패턴이 나타나는지 확인
3. 중복된 부분 처리: 패턴이 중복될 경우를 고려하여 인덱스를 이동

 

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 입력
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        String s = br.readLine();

        int cnt = 0;
        int patternLength = 2 * n + 1;
        int i = 0;

        while (i <= m - patternLength) {
            int j = 0;
            while (j < patternLength && s.charAt(i + j) == (j % 2 == 0 ? 'I' : 'O')) {
                j++;
            }
            if (j == patternLength) {
                cnt++;
                i += 2;  // 중복된 부분을 고려하여 2칸 이동
            } else {
                i += (j == 0 ? 1 : j);
            }
        }

        // 출력
        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
        br.close();
    }
}