[동적계획법]2.와일드카드

종만북 8장 동적계획법. 8.2. WILDCARD

 

https://algospot.com/judge/problem/read/WILDCARD

algospot.com :: WILDCARD

 

 

컨셉

처음엔 그냥 *만나면 다음글자 검색하면 되겠지~하고 단순하게 풀다가 예제 세번째에서 틀렸다.

책을 보고 힌트를 얻었다. *를 기준으로 단어를 나눈다. 각 단어마다 검사한다.

예) t*l?*o*r?ng*s  → t* / l?* / o* / r?ng*/ s

 

초안

내가 쓴 답 (정답, 0ms)

/**
 * @name    8.2.와일드카드
 * @ID      WILDCARD
 * @date    2019-08-06
 * @author  Sunmon
 */

#include <iostream>
#include <cstring>
#include <set>
using namespace std;

int cache[100][100];
string W, S;
int N;


//와일드카드의 w번째, 문장의 s번째 글자부터 비교하여
//패턴이 끝까지 일치하는지 여부를 리턴한다
bool match(int w, int s)
{
    //base case: 와일드카드 끝까지 검사했을 때 
    if(w==W.length()) return (s == S.length());

    //캐시
    int& ret = cache[w][s];
    if(ret != -1) return ret;

    //?나 글자가 일치하는 경우 -> 다음 글자 검사
    if(W[w] == '?' || W[w] == S[s]) return ret = match(w+1, s+1);

    //*을 만난 경우 다음 와일드카드로 넘기거나, 다음 글자로 넘긴다
    if(W[w] == '*')
        return ret = (match(w+1,s) || (s<S.length() && match(w, s+1)));

    //불일치하는 경우
    return ret = 0;
}

int main()
{
    int C;
    cin >> C;
    while(C--)
    {
        cin >> W >> N;

        //사전 순으로 출력하기 위해 set 사용
        set<string> ans;

        while(N--)
        {
            memset(cache, -1, sizeof(cache));
            cin >> S;
            if(match(0, 0)) ans.insert(S);
        }

        for(auto& a: ans) cout << a << endl;
        ans.clear();
    }
}

 

주의

- 캐시 초기화 하기 :: memset

- answer 초기화 하기 :: 정답으로 쓸 변수, 컨테이너