종만북 와일드 카드(WildCard) C++ 풀이 (코드제공)

1. 문제 설정 확인

종만북 문제 링크 : WildCard

이 문제에선 와일드카드가 문자열 안에 포함되어있는 (예 : “app*e”) 문자열이 다른 문자 (예 : “apple”)과 같다고 정의될 수 있는지 판단하는 문제다.

솔직히 DP에서의 문자열 비교는 조금 꺼려진다. 속도 제한도 빡빡해질 뿐더러, 그냥 (…) 문자열이 싫다. 그런 면에서 WildCard는 어려운 문제라고 판단된다. 이 문제에서의 와일드 카드란 총 2개로 :

1. ? : 딱 하나의 문자 (char)만 치환해주는 녀석

2. * : length 1 이상의 문자 혹은 문자열을 치환해주는 녀석

이렇게 두 개의 와일드카드가 존재한다. 먼저 어떠한 경우에 true가 return 되는지 보자.

0. 공통 조건 : 비교하는 문자열의 끝에 도달하여야 한다.

1. 제일 마지막에 온게 ? 이거나 같은 문자 (예 : “apple”이거나 “appl?”) 인 경우.

2. 제일 마지막에 온 게 * 문자거나, * 문자의 연장인 경우 (예 : “ap” 이거나 “appl“)인 경우.

1번에 대해서는 누구도 불만이 없을 것이다. 다만 조금 까다로운게 2번 조건이다. *는 문자를 하나만 치환할수도, 1 < n 의 어떤 길이도 치환할 수 있기 때문이다. 일단 다른 조건부터 해결해보자.

1. int&ret으로 cache[x][y]를 호출한다.
1. 만약 방문한 적 있다면 (실패한 경우에는 0, 성공한 경우에는 1)을 즉시 리턴해준다.
1. 아직 대상 문자와 비교 문자중 하나라도 끝에 도달하지 않은 경우가 있다면, 또 그 둘의 다음 문자가 일치한다면(혹은 와일드카드 ?라면)다음 문자 비교를 위해 재귀호출한다.
1. 만약 대상 문자의 끝에 왔다면, 비교 문자도 끝에 왔는지 확인하고 1을 return한다.
1. 만약 현재 대상 문자가 와일드카드 *라면, 와일드카드 *를 유지하고 비교 문자의 다음 문자를 검사하는 경우와 와일드카드를 넘어 두 문자 다 다음 문자를 비교하는 경우, 두 번의 재귀호출을 OR로 묶어 결과값을 반환한다.
1. 만약 2~5중 아무것도 아니라면, 이는 와일드카드도 아니고 두 문자가 일치하는 경우도 아닌 실패의 경우이므로 ret = 0값을 return하도록 한다.

3. 해답 코드

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

int cache[101][101];

int solution(string target, string tmp, int a, int b, int tmpSize, int targetSize){
    int& ret = cache[a][b];
    if(ret != -1) return ret;
    //방문한 적이 있다면 바로 return
    while(a < targetSize && b < tmpSize && (target[a] == '?' || target[a] == tmp[b])) {
        ret = solution(target, tmp, a + 1, b + 1, tmpSize, targetSize);
        return ret;
    }
    // ? 와일드카드인경우
    if(a == targetSize){
        ret = (b == tmpSize);
        return ret;
    }
    // a끝에 도달한경우
    if(target[a] == '*'){
        if((b < tmpSize && solution(target, tmp, a, b+1, tmpSize, targetSize)) || (a < targetSize && (solution(target, tmp, a+1, b, tmpSize, targetSize)))){
            //b+1 = a는 계속 *로 머물고 b의 다음칸 대응 검사, a+1 = 이제 * 스킵하고 a의 다음 문자열 검사(사이즈 체크 필요)
            ret = 1;
            return ret;
        }
    }
    ret = 0;
    return ret;
}

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        string target;
        cin >> target;
        int k;
        cin >> k;
        vector<string> ans;
        for(int j = 0; j < k; j++){
            memset(cache, -1, sizeof(cache));
            string tmp;
            cin >> tmp;
            if(solution(target, tmp, 0, 0, tmp.size(), target.size()) == 1){
                ans.push_back(tmp);
            }
        }
        sort(ans.begin(), ans.end());
        for (auto e : ans) {
            cout << e << "\n";
        }
    }
}

P.S. 8장에선 이 문제와 후에 나오는 Quantization 문제가 가장 어려웠다..

Source

종만북, 2022.07.22
CLion