[JAVA] DP: 와일드카드(WildCard)

서정범·2023년 4월 6일
DP
0

코딩테스트

목록 보기
2/3
post-thumbnail

와일드 카드

해당 문제는 종만북에서도 언급되어 있다는 문제이고, 제가 현재 보고 있는 책에서도 나와있는 문제입니다. 기본 방식으로는 완전탐색을 사용해서 문제를 푸는데 그렇게 했을 경우 시간복잡도가 굉장히 높게 나옵니다. 그것을 Memoization을 사용해서 해결을 하고, 현재 여기서 보일 방식은 3가지 입니다.

  1. 완전 탐색 방식
  2. DP를 사용한 재귀 방식
  3. DP를 사용한 반복문 방식

개인적으로, 2번이 Top-Down방식이고, 3번이 Bottom-UP방식인지는 모르겠다.

일단 알고스팟에 나와있는 문제를 예시로서 가져오겠습니다.

문제

와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 포함한다.

와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 0 글자 이상의 어떤 문자열에도 일치한다고 본다.

예를 들어 와일드 카드 he?p 는 파일명 help 에도, heap 에도 매치되지만, helpp 에는 매치되지 않는다. 와일드 카드 p 는 파일명 help 에도, papa 에도 매치되지만, hello 에는 매치되지 않는다.

와일드카드 문자열과 함께 파일명의 집합이 주어질 때, 그 중 매치되는 파일명들을 찾아내는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 10) 가 주어진다. 각 테스트 케이스의 첫 줄에는 와일드카드 문자열 W 가 주어지며, 그 다음 줄에는 파일명의 수 N (1 <= N <= 50) 이 주어진다. 그 후 N 줄에 하나씩 각 파일명이 주어진다. 파일명은 공백 없이 알파벳 대소문자와 숫자만으로 이루어져 있으며, 와일드카드는 그 외에 * 와 ? 를 가질 수 있다. 모든 문자열의 길이는 1 이상 100 이하이다.

출력

각 테스트 케이스마다 주어진 와일드카드에 매치되는 파일들의 이름을 한 줄에 하나씩 아스키 코드 순서(숫자, 대문자, 소문자 순)대로 출력한다.

예제 입력

2
he?p
3
help
heap
helpp
*p*
3
help
papa
hello

예제 출력

heap
help
help
papa

보통 이와 같이 문제가 주어집니다.

해당 문제를 푸는 코드를 보여준다기 보다, 이 문제를 해결하는 방법에 대해서 언급할 것입니다.

완전 탐색 방식

먼저, 첫 번째 방법인 완전 탐색 방식을 사용했을 경우 어떻게 문제를 해결하는지 살펴보겠습니다.

완전 탐색의 경우 와일드 카드의 문자열 W와 비교 문자열 S를 하나씩 비교해나가면서 '*'가 나왔을 때 모든 경우의 수를 전부 확인하는 방법이라고 생각하면 됩니다.

예를 들어, 와일드 카드: he*pler, 비교할 카드: helingpler일 때

*를 만난 순간부터 해당 문자 뒤의 문자열이 비교할 카드에 언제 나오는지 전부 확인하는 것입니다.

3번째 비교 순간에 만났으니 비교할 카드에서는 현재 문자가 l일 것입니다. 따라서, 비교는 다음과 같이 합니다.

(pler, lingpler) (pler, ingpler) (pler, ngpler) ... (pler, r) 이러한 식으로 전부 체크를 해버립니다.

일단 코드부터 확인해 봅시다.

 public class Main {
  static boolean perfect_match(String pat, String txt) {
    int pos = 0;
    int patLen = pat.length();
    int txtLen = txt.length();
    while (pos < patLen && pos < txtLen && (pat.charAt(pos) == txt.charAt(pos) || pat.charAt(pos) == '?'))
      pos++;
    if (pos == patLen)
      return pos == txtLen;
    if (pat.charAt(pos) == '*')
      for (int skip = 0; pos + skip <= txtLen; skip++)
        if (perfect_match(pat.substring(pos + 1), txt.substring(pos + skip)))
          return true;
    
    return false;
  }
}

이와 같이 코드가 구현됩니다.

만약, 극단적인 경우 와일드 카드: *a, 비교할 카드: aaaaaaaaaab 이러한 경우가 주어졌을 때, 매우 많은 반복문이 실행될 것입니다.

해당 방식의 시간복잡도는 다음과 같이 알려져 있습니다.

O(N)=O(N3)O(N) = O(N^3)

DP를 사용한 재귀 방식

위의 방식에서 Memoization을 사용해서 시간 복잡도를 줄여주는 방법입니다.

이 방식은 종만북에서 언급되어 있는 것 같습니다.

위의 방식에서 보면 같은 문자를 반복적으로 비교하는 상황이 나올 수 있을 것처럼 보입니다.

그래서 만약 각각의 특정 Index에서 확인한 경우 그것을 DP에 저장하여 그 이후 확인한 위치가 나온다면 기존에 확인했던 결과값을 사용하는 방식입니다.

public class WildCard_JongManBook {
  static int[][] dp = new int[101][101];
  static String W;
  static String S;

  static void init_dp(int N) {
    for (int i = 0; i <= N; i++) {
      for (int j = 0; j <= N; j++) {
        dp[i][j] = -1;
      }
    }
  }

  // 확인 안했을 경우에 -1, 확인 했지만 아닌 경우 0, 맞는 경우 1
  static int matched_dp(int w, int s) {

    if (dp[w][s] != -1) return dp[w][s];

    // W[w]와 S[s]를 맞춰나간다
    if (w < W.length() && s < S.length() && (W.charAt(w) == S.charAt(s) || W.charAt(w) == '?'))
      return dp[w][s] = matched_dp(w + 1, s + 1);

    // 위의 조건에서 아닌 경우는 3가지 경우가 존재한다.
    // 1. 모두 검사한 경우, 2. '*'가 나온 경우, 3. 글자가 다른 경우

    // CASE 1
    if (w == W.length()) {
      return (s == S.length()) ? 1 : 0;
    }

    // CASE 2
    if (W.charAt(w) == '*') {
      if (matched_dp(w + 1, s) == 1 || s < S.length() && matched_dp(w, s + 1) == 1) {
        return dp[w][s] = 1;
      }
    }

    // CASE 3
    return -1;
  }
}

이 방식의 시간 복잡도는 다음과 같습니다.

O(N)=O(N2)O(N) = O(N^2)

DP를 사용한 반복문 방식

이 방식은 현재 제가 보고 있는 Dynamic 다이나믹 프로그래밍 (비전서 시리즈4)에 나와있는 방법입니다.

해당 방식의 경우 표를 이용하는데 다음과 같이 풀이를 합니다.

먼저, 주어진 패턴 문자열의 길이 + 1와 비교할 문자열의 길이 + 1만큼의 크기를 가지는 이차원 배열을 선언해 줍니다.

int형으로 하여 1, 0으로 사용해도 되지만, 저는 Boolean을 사용했습니다.

처음은 빈문자열로 생각하기 때문에 dp[0][0] = true로 설정해두고 비교를 시작합니다.

만약 문자가 다음과 같이 주어졌다고 했을 경우의 표를 그려보겠습니다.

  • 와일드 카드: "C*AT"
  • 비교 문자열: "COMPILE.DAT"

표는 다음과 같습니다. (1은 true, 0은 false입니다.)

COMPILE.DAT
100000000000
C
*
A
T

먼저, dp[0][0] = true로 채워준 다음 본격적으로 비교를 시작합니다.

해당 표에서 1로 채워질 조건은 두가지 입니다.

  1. 이전 문자 비교 값이 1이여야 합니다.
  2. 당연하게도 현재 비교하고 있는 문자가 같아야 합니다.

이 두개의 조건을 보여주는 코드는 다음과 같습니다.

if (a[i] == b[j] && dp[i - 1][j - 1]) dp[i][j] = 1;

이러한 조건을 충족하면서 C행을 채워주면 다음과 같습니다.

COMPILE.DAT
100000000000
C010000000000
*
A
T

다음의 과정이 굉장히 중요합니다.

바로 와일드 카드에서 사용되는 '*'를 만난 경우입니다.

일단 '*'의 경우 0개의 문자 ~ n개의 문자 대체가 가능한 문자입니다.

그렇다면, 이것을 어떻게 처리해야 할까요?

명확히 이해하기 위해서 현재 저 표가 의미하는 i, j를 정리하고 가야합니다.

간단하게만 보자면 다음과 같습니다.

  • i: 현재 와일드 카드의 문자열에서의 현재 Index
  • j: 비교하는 문자 카드의 문자열에서의 현재 Index

또한 현재 표 안에 있는 값들이 나타내는 것은 비교한 결과 값을 의미합니다.

비교한 결과값 즉, 비교를 했다라고 볼수 있겠네요.

그렇다면, 오른쪽으로 한칸 이동 즉, j + 1이 의미하는 것을 무엇일까요?

그것은 i와 j를 비교해서 비교할 문자열의 인덱스를 한칸 이동이라고 생각할 수 있습니다.

즉, 비교할 문자열에서 남은 문자가 하나 줄어든 것입니다.

즉, *(와일드 카드): j가 얼마만큼 움직였나 == 얼마만큼의 문자를 대체하였나

즉, *가 나온 경우 이전 행에서 1이 나온 열(0개 대체)부터 끝까지 true로 값을 넣어주면 됩니다.

그렇게 한 결과 다음과 같습니다.

COMPILE.DAT
100000000000
C010000000000
*011111111111
A
T

이제 A를 비교할 차례이네요.

A와 A가 만났을 때 왼쪽 대각선의 값(dp[i-1][j-1])도 true이고, 값도 일치하기 때문에 true가 들어갈 것입니다.

그 이후, T도 마찬가지 입니다.

최종적으로 표는 다음과 같이 그려집니다.

COMPILE.DAT
100000000000
C010000000000
*011111111111
A000000000010
T000000000001

결과적으로 dp[N][M]은 True이기 때문에 조건이 성립됩니다.

N은 와일드 카드의 문자열 길이, M은 비교할 문자열의 길이

해당 방식은 메모리를 절약하는 방식으로 와일드 카드의 행을 2로 줄여서 홀수, 짝수를 사용하여 처리할 수도 있습니다.

코드는 다음과 같습니다.

/*
 * 해당 문제는 알고스팟의 와일드 카드 문제를 기반으로 책에 나와있는 로직대로 풀어본 예시코드입니다.
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class WildCard {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int C = Integer.parseInt(br.readLine());

    // 테스트 카운트만큼 실행
    while (C-- > 0) {
      // 와일드 카드 문자열 입력 받기 
      String W = br.readLine();

      // 주어지는 문자열의 갯수 입력 받기
      int N = Integer.parseInt(br.readLine());

      String[] S = new String[N];

      // 문자열 입력 받기
      for (int i = 0; i < N; i++) {
        S[i] = br.readLine();
      }

      ArrayList<String> str = new ArrayList<>();
      dp_match(W, S, str);

      // 아스키 코드의 순번에 맞게 출력 (오름차순 정렬)
      Collections.sort(str);
      for (String s : str) System.out.println(s);
      str = null;
    }
  }

  static void dp_match(String W, String[] S, ArrayList<String> str) {

    for (int idx = 0; idx < S.length; idx++) {
      // 와일드 카드를 행으로, 비교 문자열을 열로 생각하고 첫뻔째 열은 빈 문자열 그 이후부터 문자당 한칸씩 boolean값으로 차지.
      boolean[][] dp = new boolean[2][101];

      int w = W.length();
      String curStr = S[idx];
      int s = curStr.length();

      // 빈 문자열은 true로 설정 
      dp[1][0] = true;

      int i, j;
      for (i = 0; i < w; i++) {
        // 매번 해당 dp 테이블은 초기화 
        Arrays.fill(dp[i % 2], false);

        boolean edit = false;
        if (W.charAt(i) == '*') {
          for (j = 0; j <= s && !dp[1 - i % 2][j]; j++);
          // '*'의 경우 0개의 문자가 와도 되기 때문에 j + 1부터 채워주는 것이 아니라 j부터 채워주는 것이다.
          Arrays.fill(dp[i % 2], j, s + 1, true);
          edit = true;
        }
        else {
          for (j = 0; j < s; j++) {
            // 대각선이 true이면서 문자가 같은 경우, 혹은 대각선이 true이면서 와일드 카드 문자가 ?가 나온 경우 
            if (dp[1 - i % 2][j] && (W.charAt(i) == curStr.charAt(j) || W.charAt(i) == '?')) {
              dp[i % 2][j + 1] = true;
              edit = true;
            }
          }
        }
        if (!edit) break;
      }
      if (i == w && dp[1 - i % 2][s]) str.add(curStr);
    }

  }
}

해당 코드의 시간복잡도는 다음과 같습니다.

O(N)=O(NM);O(N) = O(NM);
profile
서정범
개발정리블로그
이전 포스트

[JAVA] 백준 2482: 색상환 (DP)

다음 포스트

[JAVA] Knapsack Problem(배낭 채우기)

0개의 댓글