[Java] 백준(실버-1) 5525번 - IOIOI

문제 풀이

---

이번 문제는 문자열 문제로 문제의 서브테스크를 모두 충족해야 100점을 받을 수 있다.

아이디어 도출

처음에는 단순히 이중 for문으로 Pn 만큼 추가로 순회하며 IOI를 체크했지만, 시간초과가 발생하였다. 그래서 시간복잡도를 O(n)으로 줄이기 위해 DP 테이블을 이용하였다.

문제 풀이를 위한 아이디어는 다음과 같다.

1. Pn에 해당하는 문자열인지 확인하기 위해 S의 2번째 원소부터 순회를 시작한다.
2. S를 순회하면서, 현재 위치까지 Pn만큼의 문자열을 만들어 Pn과 같다면, DP 테이블 위치에 1씩 카운트를 누적하도록 갱신한다.
3. 이후, DP 테이블의 현재값이 N보다 크거나 같다면, Pn이 포함되어 있는 것이기에 카운트를 1씩 증가시킨다.

Pn이 S에 포함되어 있는지를 DP 테이블의 값을 보고 판단하기에 시간복잡도를 O(n)으로 줄일 수 있었다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {    

    public static void main(String[] args) throws IOException {

        try (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();
                
                // M만큼의 길이를 가지는 DP 테이블 선언
                int[] D = new int[M];
                
                // 결과 갯수를 담을 변수
                int result = 0;

                // M의 최소 길이는 IOI인 3부터 시작하기에 
                // 2번째 위치부터 Pn이 포함되는지를 확인하기 위해 순회한다.
                for(int i=2; i<M; i++) {
                    
                    // 현재 위치까지 Pn(IOI)만큼 길이가 3인 문자열을 만든다.
                    String temp = S.substring(i-2, i+1);
                    
                    // 만든 temp가 "IOI"와 같다면 DP 테이블에 카운트를 1씩 갱신한다.  
                    if(temp.equals("IOI")) {
                        D[i] = D[i-2] + 1;
                    }

                    // DP 테이블의 값이 N보다 크거나 같다면 Pn이 포함되어 있는 것이기에 result를 1씩 증가시킨다.
                    if(D[i] >= N) {
                        result++;
                    }

                }
                                
                bw.write(result+"\n");

        }

    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.