algospot WILDCARD 와일드카드

문제

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

걸린 시간

02 : 05 : 37 실패

풀이

C++

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string.h> // memset
using namespace std;

#define INF 987654321

// -1 : 값이 계산되지 않음
// 1 : 해당 입력이 서로 대응됨
// 0 : 해당 입력들이 서로 대응되지 않음
int cache[101][101];
string W, S;

// 완전 탐색 O(N^3)
// wildcard 패턴 w가 문자열 s에 대응하는지 여부를 반환
bool matchMemoized(int w, int s){
    int& ret = cache[w][s];
    if(ret != -1){
        return ret;
    }

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

    /*
    반복이 종료되는 경우
    1. w[pos]와 s[pos]의 값이 다를 때
    2. 패턴 w의 끝에 도달했을 경우
    3. 문자열 s의 끝에 도달했을 경우
    4. '*'를 만나서 종료
    */

    // 2번, 패턴에 '*' 가 없었다는 뜻으로
    if(w == W.size()){
        // 문자열과 길이가 같다면 일치한다
        return s == S.size();
    }

    // 4번, 패턴의 '*' 가 문자열의 어디까지 대응해야
    // 할 지를 for 문을 통하여 확인
    if(W[w] == '*'){
        for(int skip = 0; s+skip <= S.size(); skip++){
            if(matchMemoized(w+1, s+skip))
                return ret = 1;
        }
    }

    // 2, 4를 제외한 경우는 모두 대응되지 않음
    return ret = 0;
}

int main(){
    int tc;
    scanf("%d", &tc);
    while(tc--){
        cin >> W;

        vector<string> result;

        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            cin >> S;
            memset(cache, -1, sizeof(cache));
            if(matchMemoized(0, 0))
                result.push_back(S);
        }

        sort(result.begin(), result.end());
        for(int i = 0; i < result.size(); i++)
            cout << result[i] << endl;
    }
    return 0;
}

조금 심화된 dp 문제를 풀어본 경험이 없어서일까 어떻게 부분 문제로 나누어 완전탐색을 해야 하는지 감이 오질 않았다.

종만북 풀이를 보고 하나하나 따라가 보았는데 복잡도를 O(n²) 까지 줄일 수 있는 최적의 분해방법까지는 이해하기가 어려웠다.

정답이 되기 위한 경우의 수를 따져보는 과정부터 재귀함수 구조를 설계하는 것 까지 스스로 생각하여 풀이하려면 정말 많은 문제를 풀어봐야겠다는 생각이 들었다.