[동적 계획법] WILDCARD 와일드 카드

동적 계획법을 적용한 문제 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstring>
 
#define UNTRAVELED -1
#define NO 0
#define YES 1
 
int cache[100][100];
std::string files[50];
std::string W{""};
std::vector<int> wildIndex;
 
// ? = whatever char
// * = whatever string
 
void inputInitialize();
int bruteWildCard(std::string, int, int);
int wildCard(std::string, int, int, int);
 
 
void printFile(int count)
{
    std::sort(files, files + count);
    for(int i = 0; i < count; i++)
        std::cout<<files[i]<<std::endl;
}
 
int main(void)
{
    int testCase{0}, n{0}, count{0};
    std::string fileName{""};
    std::cin>>testCase;
    for(int i{0}; i < testCase; i++)
    {
        wildIndex.clear();
        getchar();
        inputInitialize();
        std::cin>>n;
        
        count = 0;
        for(int j{0}; j < n; j++)
        {
            std::cin>>fileName;
            memset(cache, UNTRAVELED, sizeof cache);
            if(wildCard(fileName, 0, 0, 0) == YES)
            {
                files[count] = fileName;
                count++;
            }
        }
        printFile(count);        
    }
}
void inputInitialize()
{
    char c{' '}, d{' '};
    int i = 0;
    W = "";
    while(((c = getchar()) != '\n'))
    {
        if(d == '*' && c=='*') continue;
 
        if(c == '*')
        {
            wildIndex.push_back(i);
            d = '*';
        }
        else
            d = ' ';
 
        W += c;
        i++;
    }
}
int bruteWildCard(std::string file, int lo, int hi)
{
    int wsize = hi - lo;
    if(file.size() != wsize) return NO;
    for(int i = lo; i < hi; i++)
    {
        if ((W[i] != '?') && (file[i - lo] != W[i]))
            return NO;
    }
    return YES;
}
int wildCard(std::string file, int flo, int lo, int wildIndexTour)
{
    int wildStart{0}, leftNum{0};
    int& ret = cache[lo][flo];
    char wildNext{0};
//기저사례
    if(ret =! UNTRAVELED) return ret;
    if(wildIndexTour == wildIndex.size()) return bruteWildCard(file.substr(flo), lo, W.size());
    
    wildStart = wildIndex[wildIndexTour];
    wildNext = wildStart + 1;
    leftNum = wildStart - lo;
//왼쪽부분이 '*'이전문자열과 일치하는지
    if (bruteWildCard(file.substr(flo, leftNum) ,lo, wildStart) == NO) 
        return ret = NO;
//'*'이 문자열끝일경우 YES
    if (wildNext == W.size())
        return ret = YES;
//'*'의 오른쪽을판단한다
    ret = NO;
    for(int i = flo + leftNum ; i < file.size(); i++)
    {
        if(W[wildNext] == file[i] || W[wildNext] == '?')
            ret = wildCard(file, i, wildNext, wildIndexTour + 1);
        if(ret)
            return ret;
    }
    return ret;
}

 

1. 이 문제는 '*' 에서 중복 문제가 발생하게 된다

    '*'의 개수가 여러개일 경우

    와일드 카드의 앞쪽 '*' 들 각각 파일명에 해당하는 문자열의 길이에 따라

    뒤쪽 '*' 들이 중복 계산될 수 있다.

2. 해당 문제는 wildcard의 '*'을 기준으로 분할 할 수 있다.

   

    wildcard를 입력받을때 '*'의 위치를 기억하고

   

    앞에서 부터 차근 차근 '*'을 찾아 이것을 기준으로 왼쪽 부분.  오른쪽 부분 으로

    분할 한다.

   

    - 왼쪽부분은 항상 '*'이 포함되지 않은 문자열이므로

      ('*'이 있어도 이미 해결한 문제이다)

     파일명은 앞에서부터 와일드 카드 '*'의 왼쪽부분과 문자열을 비교하는데 큰 어려움이 없다.

    

    - 와일드 카드 '*' 오른쪽 부분은

    '*'으로 생략되는 부분과 wildcard를 재귀호출하여 다음 '*' 기준으로 문자열을 해독한다.

 

    '*'으로 생략되는 부분은 '*'의 인덱스 + 1 에 해당하는 문자와

    파일명의 '*'의 왼쪽부분과 비교하고 남은 나머지 문자열부터 끝까지

    비교하며 동일할 경우 그 이전까지 모든 문자가 '*'에의해 생략된다고 가정하여 

    다음 부분 문제로 넘어간다.

 

3. 기저 사례는 다음과 같다

    - 해당 단계에서 '*'이 없을경우 -> 완전탐색으로 비교한다.

    - 메모이제이션 적용 => 이미 계산했을경우

 

4. 메모이제이션 적용

    해당 문제는 함수가 호출 될때의 파일명의 시작점과,

    와일드 카드의  시작점을 좌표로 가지는 배열을 생성하여

    메모이제이션을 적용할 수 있다.

    

    함수가 호출 될때

    와일드 카드의 시작점은 처음 호출을 제외하고 '*'의 바로 앞이다.

    파일명의 시작점은 처음 호출을 제외하고 '*'로 생략되는 문자열 바로 앞이다.

 

    그러므로

    파일명의 시작점이 몇번째 '*' 로부터 생략된 이후 문자열 일치 여부 기록할 수 있으며

    이는 1.에서 중복되는 계산을 피할 수 있게된다.

    

   

WILDCARD