[Algorithm/Java] 백준 5525번 - IOIOI

---

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

---

📌 문제

문제 유형

• 문자열

문제 설명

입력

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

1
13
OOIOIOIOIIOII

출력

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

4

🔍 문제 풀이

처음엔 문자열 생성 + 포함 여부로 시도했다.

처음엔 String.repeat()을 사용해서 Pn 패턴을 만들고, s.contains(line)으로 포함 여부를 세는 방식으로 접근했었다.

String pattern = "IO".repeat(n) + "I";
int cnt = 0;
for (int i = 0; i <= s.length() - pattern.length(); i++) {
    if (s.substring(i, i + pattern.length()).equals(pattern)) {
        cnt++;
        i += 2;
    }
}

하지만 반복문 안에서 substring()과 equals()를 계속 호출 → 시간복잡도 O(N*M)이 되어..

그래서 슬라이딩 윈도우 방식으로 전환하였다.

• Pn은 IOI가 N번 연속된 구조
• 즉, “IOI”라는 패턴이 N번 연속 등장하는지 확인하면 된다
• 윈도우를 오른쪽으로 밀면서 “IOI”가 등장할 때마다 count 하기!

int i = 1;
int cnt = 0;
int pattern = 0;

while (i < m - 1) {
    if (s.charAt(i - 1) == 'I' && s.charAt(i) == 'O' && s.charAt(i + 1) == 'I') {
        pattern++;
        if (pattern == n) {
            cnt++;
            pattern--;  // 겹치는 경우 고려
        }
        i += 2;
    } else {
        pattern = 0;
        i++;
    }
}

📎 슬라이딩 윈도우란?

슬라이딩 윈도우는 연속된 일정 범위를 유지하면서 한 칸씩 이동하며 처리하는 알고리즘 기법

• 배열이나 문자열 등에서 고정된 길이 or 조건을 만족하는 구간을 빠르게 탐색할 때 사용된다.
• 중복 계산 없이 효율적으로 문제를 해결할 수 있다.
• 이 문제에서는 “IOI” 구조를 한 칸씩 슬라이딩하며 확인하는 방식으로 활용

📌 놓친 점

겹치는 패턴을 고려해서 pattern-- 처리 필요

• IOIOIOI처럼 겹치는 구조를 하나의 Pn으로만 치지 않고 여러 개로 계산하려면, pattern--을 해줘야 한다.
• 즉,
  • 한 번 Pn을 찾고 난 뒤 pattern--을 해줌으로써,
  • 다음 IOI가 나오면 pattern++ 했을 때 바로 다시 pattern == n이 되게 하려는 것!

💻 전체 코드

import java.io.*;

public class Main {

    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 s = br.readLine();

        int i = 1;
        int cnt =0;
        int pattern = 0;
        while(i < m-1){
            if(s.charAt(i - 1) == 'I' && s.charAt(i) == 'O' && s.charAt(i+1) == 'I'){
                pattern++;
                if(pattern == n) {
                    cnt ++;
                    pattern--; // 중복 패턴 추가하기 위함
                }
                i += 2;

            } else{
                pattern=0;
                i++;
            }
        }

        System.out.println(cnt);
    }
}