[알고스팟 WILDCARD] 와일드카드 C++

algospot.com/judge/problem/read/WILDCARD

algospot.com :: WILDCARD

너무 어려웠다... 동적프로그래밍 진짜 어려웠던듯

 

풀이법은 한자리씩 대응시켜보고

*를 만나면 *까지 대응되는 문자열을 구하고

그다음부터 또 한개씩 대응시켜보는것

 

처음에 시간초과나서 두번째는 메모이제이션 사용했슴..

 

 

재귀 정말 헷갈려 ㅜ

 

 

시간초과남(풀이x)

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
bool search(string wildcase, string namecase) {
    int idx = 0;
    //한글자씩 비교과정
    while (idx < wildcase.size() && idx < namecase.size() &&
        (wildcase[idx] == '?' || wildcase[idx] == namecase[idx]))
        idx++;
    //대응이 안되면 왜 안되는지 확인
    //인덱스가 와일드카드 사이즈 범위 넘었을때
    if (idx == wildcase.size()) return idx == namecase.size();
 
    if (wildcase[idx] == '*')
        for (int skip = 0; idx + skip < namecase.size(); skip++)
            if (search(wildcase.substr(idx + 1), namecase.substr(idx + skip)))
                return true;
 
    return false;
 
}
int main() {
    int c, n;
    string w, s;
    cin >> c >> w >> n;
    while (c--) {
        while (n--) {
            cin >> s;
            if (search(w, s) == true)
                cout << s << '\n';
        }
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
 
 
using namespace std;
int dp[101][101];
string wild, name;
 
int search(int w, int s) {
 
    int result = dp[w][s];
    if (result != -1) return result;
    //한글자씩 비교과정
    while (w < wild.size() && s < name.size() &&
        (wild[w] == '?' || wild[w] == name[s])) {
        w++;
        s++;
    }
 
    //대응이 안되면 왜 안되는지 확인
    //인덱스가 와일드카드 사이즈 범위 넘었을때
    if (w == wild.size()) return dp[w][s] = (s == name.size());
 
    if (wild[w] == '*')
        for (int skip = 0; s + skip <= name.size(); skip++)
            if (search(w + 1, s + skip))
                return dp[w][s] = 1;
 
    return dp[w][s] = 0;
 
}
int main() {
    int c, n;
 
    cin >> c;
    while (c--) {
        vector<string> words;
        cin >> wild;
        cin >> n;
 
 
        while (n--) {
            cin >> name;
            memset(dp, -1, sizeof(dp));
            if (search(0, 0) == 1)
                words.push_back(name);
        }
        sort(words.begin(), words.end());
        for (int i = 0; i < words.size(); i++)
            cout << words[i] << '\n';
    }
    return 0;
}