[algospot] wildcard

문제링크 입니다

[wildcard] 문제

와일드카드 패턴과 함께 파일명의 집합이 주어질 때, 그중 패턴에 대응되는 파일명들을 찾아내는 프로그램을 작성하세요.

먼저 완전탐색 알고리즘으로 문제를 해결하였습니다. algospot 통과됨;;; 88ms

입력 값은 다음과 같습니다

2
he?p
3
help
heap
helpp
*p*
3
help
papa
hello

출력값은 다음과 같습니다.

heap
help
help
papa

전체 코드는 다음과 같습니다.

//
//  wildcard.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/09/14.
//
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;

ifstream fin("wildcard.txt");

bool check(const string& wildcard, const string& filename){
    int pos = 0;
    while(pos < wildcard.size() && pos < filename.size() &&
          (wildcard[pos]=='?' || (wildcard[pos] ==filename[pos] ))){
        pos ++;
    }
    if(pos == wildcard.size()){
        return pos==filename.size();
    }
    if (wildcard[pos] == '*'){
        for(int i=0; i+pos <= filename.size(); ++i){
            if(check(wildcard.substr(pos+1), filename.substr(i+pos)))
                return true;
        }
    }
    return false;
}

void wild(string wildcard, vector<string>& filename){
    vector<string> result;
    for(int i=0; i<filename.size(); i++){
        if(check(wildcard, filename[i])){
            result.push_back(filename[i]);
        }
    }
    sort(result.begin(), result.end());
    for(int i=0; i<result.size(); i++){
        cout << result[i] << endl;
    }
}

int main(int argc, const char * argv[]) {
    int Test_case;
    fin >> Test_case;

    for (int i=0; i< Test_case ; i++){
        string wildcard;
        int num;
        fin >> wildcard;
        fin >> num;
        vector<string> filename;
        for(int j=0; j<num; j++){
            string temp;
            fin >> temp;
            filename.push_back(temp);
        }
        wild(wildcard, filename);
    }
    return 0;
}

메모이제이션 써서 만든거. 4ms WOW

//
//  wildcard.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/09/14.
//
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

ifstream fin("wildcard.txt");
string W,F;
int cache[101][101];
bool check(int w, int f){
    int &ret = cache[w][f];
    if(ret!=-1) return ret;
    while(w < W.size() && f < F.size() &&
          (W[w]=='?' || (W[w] ==F[f] ))){
        w++;
        f++;
    }

    if(w == W.size()){
        return ret = (f==F.size());
    }

    if (W[w] == '*'){
        for(int i=0; i+f <= F.size(); i++){
            if(check(w+1, i+f))
                return ret=1;
        }
    }
    return ret = 0;
}

void wild(string wildcard, vector<string>& filename){
    vector<string> result;
    W = wildcard;
    for(int i=0; i<filename.size(); i++){
        memset(cache, -1, sizeof(cache));
        F = filename[i];
        if(check(0, 0)){
            result.push_back(filename[i]);
        }
    }
    sort(result.begin(), result.end());
    for(int i=0; i<result.size(); i++){
        cout << result[i] << endl;
    }
}

int main(int argc, const char * argv[]) {
    int Test_case;
    fin >> Test_case;

    for (int i=0; i< Test_case ; i++){
        string wildcard;
        int num;
        fin >> wildcard;
        fin >> num;
        vector<string> filename;

        for(int j=0; j<num; j++){
            string temp;
            fin >> temp;
            filename.push_back(temp);
        }
        wild(wildcard, filename);
    }
    return 0;
}