[JAVA / 자바] 백준 5525번_IOIOI

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

5525번: IOIOI

---

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

public class Main {
    static int N, M, tmpN = 0, cnt = 0;
    static String S;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        S = br.readLine();
        for (int i = 1; i < M - 1; ) {
        //최소 단위인 3개씩 검사
            if(S.charAt(i-1) == 'I' && S.charAt(i) == 'O' && S.charAt(i+1) == 'I'){
                tmpN++; //단위만큼 같으면 n+1
                if(tmpN == N){ //해당 문자열과 일치하면 +1
                    tmpN--;
                    cnt++;
                }
                i += 2; //같으면 2개 뒤로 미뤄서 다시 검사
                continue;
            }//일치하지 않으면 초기화
            tmpN = 0;
            i++;
        }
        System.out.println(cnt);
    }
}

💡 문자열

과정

 - Pn = 'O'이 n개인 문자열 

    - Pn = I + "OI'.repeat(n)

- S안에 Pn이 몇 군데 포함되어있는지 카운팅

# 1트 : 틀림
1. Pn을 생성한다
2. S 앞부터 탐색해 나가며 Pn 찾으면 cnt++
3. S에서 Pn과 일치하는 제일 처음 문자열을 찾아, 해당 부분에서 맨 앞 "IO" 제거
    → 어차피 Pn은 I부터 시작 & 중복 카운팅을 막고, 겹치는 부분을 활용하기 위해

<반례> OOIOIIOIOIOIOIOIOIOIOOIOI →   OOIIOIOIOIOIOIOIOOIOI →  OOIIOIOIOIOIOIOOIOI 

   : 이런 식으로 애니팡처럼 하나 터지면 앞에서 남은거랑 다시 만나서 카운팅 되는 예외 발생

    →  replace 대신 subString 사용

# 2트 : 50점 ^^...
- String.indexOf의 시간 복잡도가 O(M)이고, while문이 O(M)이라 사실상 O(M^2)로 시간초과 발생한 듯

 

최종 풀이

- 최소 단위인 P1 = "IOI" 기준으로 생각하면, P2 = "IOI" + "IOI" 로 볼 수 있음

   ➡️ 앞에서부터, 진행해 나가되, 3개씩 기준으로 묶어서 검사한다.

- 일치하면 n을 증가시켜 주고, n == N일 경우 카운팅 하고 2칸 뒤부터 다시 시작

EX) IOIOIOI에서 IOIOI(N=2)를 찾는 경우, S[0 ~ 2] 까지 일치 => tmpN++, idx+=2

   → S[2 ~ 4]까지 일치; tmpN++ OR 일치하지 않으면 tmpN 개수 0으로 초기화

   →  tmpN = 2이므로 count +1 && tmpN -= 1 (그 다음 검사시 앞에 "IO" 빼고 다시 검사하므로)