WILDCARD 와일드카드

나의 풀이

‘*’ 문자가 해결에 가장 어려운 점으로 다가온 문제였다. 책에서는 *을 해결하기 위해 문제를 나누는 것을 권장했다. DP는 분할정복의 확장판임을 다시한번 상기시키는 부분이다. m개의 *을 기준으로 문자열을 나누게 되면 m+1조각의 문제로 나눌 수 있다.

분기 이후에는 종료하는 경우의 수를 모두 따져 코드로 작성하면 답안이 된다.

힌트 : 문자열의 비교라는 비교적 간단한 알고리즘과 *과 ?의 조건을 제대로 이해하여 문제를 나누어 다이나믹 프로그래밍으로 작성하면 된다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int mem[101][101];
string W, S;

void resetMem() {
    for (int i = 0; i < 101; i++)
        for (int j = 0; j < 101; j++)
            mem[i][j] = -1;
}

int isPossible(int wIdx, int sIdx) {
    if (mem[wIdx][sIdx] != -1) {
        return mem[wIdx][sIdx];
    }

    int& ret = mem[wIdx][sIdx];

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

    if (wIdx == W.size()) {
        return ret = (sIdx == S.size());
    }

    if (W[wIdx] == '*') {
        for (int mv = 0; mv + sIdx <= S.size(); mv++) {
            if (isPossible(wIdx + 1, sIdx + mv)) {
                return ret = true;
            }
        }
    }

    return ret = false;
}

int main() {
    int C, N;
    cin >> C;
    while (C--) {
        cin >> W;
        cin >> N;
        vector<string> ans;
        for (int _ = 0; _ < N; _++) {
            resetMem();
            cin >> S;
            if (isPossible(0, 0)) {
                ans.push_back(S);
            }
        }
        sort(ans.begin(), ans.end());
        for (string a : ans) {
            cout << a << "\n";
        }
    }
}