WILD CARD

WILD CARD

헷갈리는 부분이 은근히 많았다... 뭔가 제대로 정리를 하지 않고 풀었다.

종만북에서 DP문제로 정해져있지만, 완전탐색을 이용해도 시간내에 해결할 수 있는 문제이다.

이 문제에서 핵심은 * 를 어떤식으로 해결하느냐이다.

나는 for문을 이용해서 *을 0칸부터 비교할 string의 끝칸까지 돌리는 방법으로 문제를 해결했다.

    //하나씩 비교 (맨마지막까지)

    if (wc[wc_idx] == '*') {

        for (int i = str_idx; i <= str.size(); i++)

        {

            go(wc_idx + 1, i);

        }

    }

비교를 시작하는 부분에서 그 문자의 최대길이까지 * 를 매칭했다.

이 부분을 처음에는 go 의 매개변수로 i+1 을 넘겼고, for문에서  i < str.size() 까지만 실행시켰었다.

매개변수를 i+1 로 넘길 경우, * 가 공란을 의미하는 경우를 커버하지 못했다.

또한 i < str.size() 로 하지 않으면 * 이 나머지 모든 칸을 의미하는 경우를 커버하지 못했다.

그리고 재귀함수를 빠져나오는 조건으로는 4가지 조건을 이용했다.

1. wc_idx 와 str_idx 가 딱 맞게 자신들의 문자의 끝을 가리키는 경우 성공.

2. str_idx 는 str의 끝을 가리키지만 wc_idx가 끝이 나지 않은 경우, 오답이라고 생각할 수 있지만 남은 wc 문자들이 모두 * 일 경우에는 정답

이 된다. 따라서 이 경우는 if문으로 처리해서 재귀함수를 더 돌리도록 하였다.

3. wc_idx 는 끝을 가리키지만 std_idx 가 끝이 나지 않은 경우는 모두 오답이라고 볼 수 있다.

4. wc 문자가 * 도 ? 도 아닌데 wc 와 str의 문자가 같지 않은 경우도 오답이라고 볼 수 있다.

그리고 아래의 경우는 정답이 확인되는 경우, 재귀함수를 빠르게 빠져나와서 시간을 단축하도록 하였다.

    if (chk == true)

    {

        return;

    }

<정답 코드>

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int n;
string wc;
string str;
bool chk;
 
void go(int wc_idx,int str_idx) {
    
    //정답이 발견된 경우 그냥 끝내기
    if (chk == true)
    {
        return;
    }
 
    //둘 다 끝났을때 정답
    if (wc_idx == wc.size() && str_idx == str.size())
    {
        chk = true;
        return;
    }
 
    //wild card는 안 끝났는데, 다른 string 변수는 끝이 났을 때
    if ((wc_idx != wc.size()) && (str_idx == str.size()))
    {
        //이때 wild card 값이 *인 경우 더 진행
        if (wc[wc_idx] == '*')
            go(wc_idx + 1, str_idx);
        else
            return;
    }
    //wild card 는 끝이 났는데 string이 남았을 때 오답
    if ((wc_idx == wc.size()) && (str_idx != str.size()))
        return;
 
    //문자가 다를 때 오답
    if (wc[wc_idx] != str[str_idx] && wc[wc_idx] != '?' && wc[wc_idx] != '*')
    {
        return;
    }
    
 
    //하나씩 비교 (맨마지막까지)
    if (wc[wc_idx] == '*') {
        for (int i = str_idx; i <= str.size(); i++)
        {
            go(wc_idx + 1, i);
        }
    }
    
    //같은 자이거나 wild card 가 ? 일 때 다음으로 넘어가기
    if (wc[wc_idx] == str[str_idx] || wc[wc_idx] == '?')
    {
        go(wc_idx + 1, str_idx + 1);
    }
 
    return;
 
 
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        vector<string> ans;
 
        cin >> wc;
        cin >> n;
 
        for (int i = 0; i < n; i++) {
            chk = false;
            cin >> str;
            go(0, 0);
            if (chk)
                ans.push_back(str);
        }
 
 
        sort(ans.begin(), ans.end());
 
        for (int i = 0; i < ans.size(); i++)
            cout <<ans[i] << endl;
    }
 
    return 0;
}