[백준 - 5015번] Is - Java

문제 링크

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

문제

티어: 골드 3
알고리즘: dp

입력

첫째 줄에 패턴 P가 주어진다. P는 1글자~100글자이고, 알파벳 소문자와 '.', '*'로만 이루어져 있다. 둘째 줄에는 디렉토리의 파일 개수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개의 줄에는 디렉토리에 있는 파일의 이름이 한 줄에 하나씩 주어진다. 파일의 이름은 1글자~100글자이고, 알파벳 소문자와 '.'으로만 이루어져 있다.

출력

패턴 P와 일치하는 파일의 이름을 입력으로 주어진 순서를 따라서 한 줄에 하나씩 출력한다.

풀이

패턴 P와 일치하는 모든 파일의 이름을 찾아야 한다.

처음에는 완탐이 가능할 줄 알고, 풀었다. 그런데 36퍼에서 TLE가 났다.

그래서 코드를 보니 와일드 패턴이 나오는 경우에 결국 하나씩 늘려가면서 스킵을 해야되기 때문에 와일드 패턴이 최대로 나오면서 최대로 실패하는 경우 시간 복잡도가 기하급수적으로 증가했다.

그래서 어떻게 해결해야 할지 생각하다가 중복 탐색하는 경우를 찾았고, dp를 활용했다.

예를 들어 현재 패턴의 위치를 가리키는 커서와 파일 이름에서 특정 문자를 가리키는 커서가 있을 때 이 커서부터 매칭되는지 안되는지는 한 번만 탐색하면 된다.

그래서 dp[A][B] -> A 패턴의 커서 위치, B 파일 이름의 커서 위치로 정의할 수 있다.

이렇게 dp를 활용하면 O(P L N)으로 풀이가 가능하다. (L은 파일 이름의 길이)

구현은 케이스를 잘 분류해서 해야된다. 이 부분은 실수할 여지가 많다고 본다. 자세한 구현은 소스 코드를 참고하길 바란다.

소스 코드

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

public class Main {
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      String pt = br.readLine();
      int N = Integer.parseInt(br.readLine());
      String[] file = new String[N];
      for(int i=0; i<N; i++) {
          file[i] = br.readLine();
      }
      
      StringBuilder sb = new StringBuilder();
      for(int i=0; i<N; i++) {
          int[][] dp = new int[pt.length() + 1][file[i].length() + 1]; //0은 방문 x, 1은 가능, 2는 불가
          if(answer(pt, file[i], dp, 0, 0) == 1) {
              sb.append(file[i]).append("\n");
          }
      }
      
      System.out.println(sb.toString().trim());
  }
  
  static int answer(String pt, String fileName, int[][] dp, int ptCursor, int fnCursor) {
      if(ptCursor == pt.length()) {
          //마지막 커서는 알파벳 또는 와일드임
          if(pt.charAt(ptCursor - 1) != '*' && fnCursor != fileName.length()) {
              //와일드가 아니라면 fnCursor 또한 fileName.length()를 가르키고 있어야됨 그렇지 않으면 false;
              return 2;
          }
          return 1;
      }
      
      if(dp[ptCursor][fnCursor] != 0) {
          //이미 방문했다면
          return dp[ptCursor][fnCursor];
      }
      
      if(pt.charAt(ptCursor) == '*') {
          dp[ptCursor][fnCursor] = answer(pt, fileName, dp, ptCursor + 1, fnCursor);
          return dp[ptCursor][fnCursor];
      }
      
      if(fnCursor == fileName.length()) {
          //패턴이 일치되지 않은 상태에서 cursor가 넘어가면 일치 x
          return 2;
      }
      
      boolean wild = true;
      if(ptCursor == 0 || pt.charAt(ptCursor - 1) != '*') {
          wild = false;
      }
      
      if(!wild) {
          //앞이 와일드가 아닌경우
          if(pt.charAt(ptCursor) == fileName.charAt(fnCursor)) {
              dp[ptCursor][fnCursor] = answer(pt, fileName, dp, ptCursor + 1, fnCursor + 1);
              return dp[ptCursor][fnCursor];
          }
      } else {
          //앞이 와일드인 경우
          for(int i=fnCursor; i<fileName.length(); i++) {
              if(pt.charAt(ptCursor) == fileName.charAt(i)) {
                  if(answer(pt, fileName, dp, ptCursor + 1, i + 1) == 1) {
                      dp[ptCursor][fnCursor] = 1;
                      return dp[ptCursor][fnCursor];
                  }
              }
          }
      }
      dp[ptCursor][fnCursor] = 2;
      return dp[ptCursor][fnCursor];
  }
}