[동적 계획법] WILDCARD

[1. 문제 재정의 및 추상화]

1. 와일드카드 패턴을 앞에서 한 글자씩 파일명과 비교해서 모든 글자 일치 시, 와일드카드 패턴이 파일명과 대응된다 말함
2. '?' 는 어떤 글자와도 대응된다 가정함
3. '*' 는 0글자 이상의 어떤 문자열에도 대응 됨.
4. 주어진 와일드카드 패턴에 대응되는 문자열 출력
5. ex)
   와일드카드 패턴 he?p 에 매치되는 문자열은 아래와 같다
   heap, help
   helpp 는 ? 가 lp 에 대응 될 수 없기 때문이다
6. 패턴이 아닌 문자열은 알파벳 대소문자와 숫자만으로 구성 됨.

 

[2. 해결 계획]

1. 완전 탐색 풀이
   

   #include <string>
   
   // w: 와일드카드 패턴
   // s: 문자열
   bool match(const std::string &w, const std::string &s)
   {
       int pos = 0;
       while (pos < w.size() && pos < s.size() &&
              (w[pos] == '?' || w[pos] == s[pos]))
       {
           // w 와 s 모두 확인 가능하고
           // 현재 패턴이 '?' 인 경우 어떤 글자와도 대응되며
           // 실제로 두 문자열에서 해당 위치의 문자는 같을 수 있다
           // 이 경우 계속 확인을 진행 함
           pos++;
       }
   
       // 위 반복문을 탈출하는 경우는
       // 1. 패턴이 끝남
       // 2. 문자열이 끝남
       // 3. 패턴 내 문자가 '*' 임 => 패턴과 문자는 다를 수 밖에 없음
       // 4. 해당 위치에서 패턴과 문자가 다름
   
       // 패턴이 끝나는 경우
       if (pos == w.size()) {
           // 문자열도 끝나야 
           // 문자열이 와일드 카드 패턴에 매칭 됨.
           return pos == s.size();
       }
   
       if (w[pos] == '*')
       {
           // 이후 남은 문자열에 대해서 검증을 진행
           // 현재 패턴이 '*' 인 경우는 그 어떤 문자에도 매칭 되므로
           // '*' 에 몇 글자를 대응해야 할지 재귀 호출하면서 확인한다.
           for (int skip = 0; pos + skip <= s.size(); skip++)
           {
               if (match(w.substr(pos+1), s.substr(pos+skip))) {
                   return true;
               }
           }    
       }
       // 그 외 경우는 모두 매칭되지 않는다.
       return false;
   }​

2. 재귀 호출 시 w 와 s 는 전체 문자열 W 와 전체 패턴 S 에 대해서 접미사(suffix) 가 된다.
3. 재귀가 발생하는 곳에서는 앞의 부분 문제가 더 이상 결과 값 계산에 영향을 주지 않는다.
   pos 앞쪽이 매칭 되었으면, 벌써 true 를 반환 했을 것이기 때문에
4. 따라서 최적 부분 구조를 만족 한다 볼 수 있다.(?)
5. 패턴과 문자열의 검사의 부분 문제가 발생하는 시점을 캐시의 key 로 사용하여 memoization 을 적용 할 수 있다.

 

[3. 계획 검증]

 

 

[4. 구현]

#include <iostream>
#include <string>

// w 와 s 의 위치에서 
// 패턴과 문자열에 각 문자가 대응되는지 확인한다.
int cache[101][101];
std::string W, S;
int match(int w, int s)
{
    int &ret = cache[w][s];
    if (ret != -1) {
        return ret;
    }

    while (w < W.size() && s < S.size() && 
          (W[w] == '?' || W[w] == S[s]))
    {
        w++;
        s++;
    }

    // 패턴에 끝에 도달함
    if (w == W.size()) {
        // 문자열도 끝에 도달한 경우 서로 대응되고
        // 그렇지 않다면 서로 대응하지 않음.
        ret = (s == S.size());
        return ret;
    }

    // 첫번째 while 에서 
    // 패턴이 '*' 여서 끝난 경우
    if (W[w] == '*')
    {
        // 문자열을 '*'에 어디까지 대응 시킬 수 있는지 확인한다.
        // W[w+1:] 과 S[s:], S[s+1:], ...
        // * 에는 어떤 문자도 대응하지 않을 수 있다.
        for (int skip=0; s + skip < S.size(); skip++)
        {
            if (match(w+1, s+skip)) {
                ret = 1;
                return ret;
            }
        }
    }

    ret = 0;
    return ret;
}

int main()
{
    int T;
    char buf[128];
    scanf("%d", &T);

    for (; T > 0; T--) {
        scanf("%s", buf);
        W = buf;
        
        int N;
        scanf("%d", &N);
        for (; N > 0; N--)
        {
            memset(cache, -1, sizeof(cache));
            scanf("%s", buf);
            S = buf;

            if (match(0, 0)) {
                printf("%s\n", buf);
            }
        }
    }

    return 0;
}

 

[5. 구현 2]

위 구현에서 두개의 반복문에 대해 재귀 호출로 바꾸어 메모아이제이션을 적용하면,

시간 복잡도를 낮출 수 있다.

 

int match(int w, int s)
{
    int &ret = cache[w][s];
    if (ret != -1) {
        return ret;
    }

    /*while (w < W.size() && s < S.size() && 
          (W[w] == '?' || W[w] == S[s]))
    {
        w++;
        s++;
    }*/
    if (w < W.size() && s < S.size() && 
          (W[w] == '?' || W[w] == S[s]))
    {
        ret = match(w+1, s+1);
        return ret;
    }

    // 패턴에 끝에 도달함
    if (w == W.size()) {
        // 문자열도 끝에 도달한 경우 서로 대응되고
        // 그렇지 않다면 서로 대응하지 않음.
        ret = (s == S.size());
        return ret;
    }

    // 첫번째 while 에서 
    // 패턴이 '*' 여서 끝난 경우
    if (W[w] == '*')
    {
        // 문자열을 '*'에 어디까지 대응 시킬 수 있는지 확인한다.
        // W[w+1:] 과 S[s:], S[s+1:], ...
        // * 에는 어떤 문자도 대응하지 않을 수 있다.
        /*for (int skip=0; s + skip <= S.size(); skip++)
        {
            if (match(w+1, s+skip)) {
                ret = 1;
                return ret;
            }
        }*/
        // '*' 에 대응되는 것이 없을 때
        if (match(w+1, s) || (s < S.size() && match(w, s+1)))
        {
            ret = 1;
            return ret;
        }
    }

    ret = 0;
    return ret;
}