[c++] 알고리즘 문제 해결 전략 1권 :: 와일드카드 (문제 ID: WILDCARD, 난이도 : 중)

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

문제

와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 포함한다.

와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 0 글자 이상의 어떤 문자열에도 일치한다고 본다.

예를 들어 와일드 카드 he?p 는 파일명 help 에도, heap 에도 매치되지만, helpp 에는 매치되지 않는다. 와일드 카드 *p* 는 파일명 help 에도, papa 에도 매치되지만, hello 에는 매치되지 않는다.

와일드카드 문자열과 함께 파일명의 집합이 주어질 때, 그 중 매치되는 파일명들을 찾아내는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 10) 가 주어진다. 각 테스트 케이스의 첫 줄에는 와일드카드 문자열 W 가 주어지며, 그 다음 줄에는 파일명의 수 N (1 <= N <= 50) 이 주어진다. 그 후 N 줄에 하나씩 각 파일명이 주어진다. 파일명은 공백 없이 알파벳 대소문자와 숫자만으로 이루어져 있으며, 와일드카드는 그 외에 * 와 ? 를 가질 수 있다. 모든 문자열의 길이는 1 이상 100 이하이다.

출력

각 테스트 케이스마다 주어진 와일드카드에 매치되는 파일들의 이름을 한 줄에 하나씩 아스키 코드 순서(숫자, 대문자, 소문자 순)대로 출력한다.

예제 입력

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

예제 출력

heap
help
help
papa

나의 답

생각의 흐름

1. 문자열 비교인데, *와 ?는 어떻게 비교하면 좋을까?

   *는 아무 문자도 없어도 되고 여러 개의 아무 문자나 와도 된다.

   ?는 하나의 아무 문자나 와도 된다.

2. *는 뒤에 문자가 오는 경우에 경우의 수가 많아진다.

   ex_) *d 에서 add가 주어졌으면 d가 2번째 d일수도 3번째 d일수도 있다.

3. 와일드 카드 문자열을 돌면서 해당 와일드 카드에 해당하는 문자가 주어진 단어에 존재하는지를 검사하자.

   1. *, ? , 문자 의 경우를 조건을 주어서 나누면 된다.
   2. 이 때, *가 왔을 경우 그 뒤에 문자가 오면 2의 ex와 같이 해당하는 문자에 대해 모두 실행해야함을 따로 구현해주자.
   3. 현재 어느 위치를 비교하고 있는지를 쉽게 나타내기 위해 와일드 카드 문자열의 pointer와 단어 문자열의 pointer를 따로 두자.

코드

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

using namespace std;

int index = 0;
int searchOthers = 0;

bool checkMatching(vector<char>& target, string& word, int tp,int wp) {
    int target_pointer = tp; // 현재 target의 몇번째 문자를 검사 중인지
    int word_pointer = wp; // 현재 word의 몇번째 문자를 검사 중인지
    int starExist = 0;
    while(target_pointer<target.size()) {
        if (target[target_pointer] == '*') {
            starExist = 1;
            target_pointer++;
            continue;
        }
        else if (target[target_pointer] == '?') {
            word_pointer++; target_pointer++;
            continue;
        }
        else {
            if (starExist) {
                vector<pair<int,int>> word_index;
                for (int j = word_pointer; j < word.size(); j++) {
                    if (target[target_pointer] == word[j])
                        word_index.push_back(make_pair(target_pointer, j));
                }
                for (int k = 0; k < word_index.size(); k++) {
                    if (checkMatching(target, word, word_index[k].first, word_index[k].second))
                        return true;
                }
                return false;
            }
            else {
                if (target[target_pointer] == word[word_pointer]) {
                    word_pointer++; target_pointer++;
                    continue;
                }
                else
                    return false;
            }
        }
    }
    if (target_pointer == target.size() && (starExist||word_pointer==word.size()))
        return true;
    else
        return false;
}

int main() {
    int c;
    cin >> c;
    cin.ignore(256, '\n');

    while (c--) {
        string word_list[50]; // 단어 리스트
        string answer_list[50]; // 정답 리스트
        index = 0;

        string w;
        getline(cin, w);

        vector<char> w_arr;
        for (int i = 0; i < w.size(); i++)
            w_arr.push_back(w[i]); // string => arr

        int n;
        cin >> n;
        cin.ignore(256, '\n');

        for (int i = 0; i < n; i++) {
            getline(cin, word_list[i]); // 단어를 받아서
            if (checkMatching(w_arr, word_list[i], 0, 0)) // 매칭되면
                answer_list[index++] = word_list[i]; // 정답 배열에 넣는다.
        }

        sort(answer_list,answer_list+index); // 정답 배열을 아스키코드 순서로 배치

        for (int i = 0; i < index; i++) {
            cout << answer_list[i] << " ";
        }
        cout << endl;
    }

}

 하나의 예를 보면 이런 식으로 진행된다. 마지막에 return true를 하게 되면 처음에 *을 만나고 d문자를 만나서 들어왔던 재귀함수로 return 되면서 true를 main함수에서의 호출문으로 return하게 된다.

 여기서 마지막에 starExist와 word를 체크하는 조건을 OR 연산해둔 이유는 target의 마지막이 *라면 word가 몇 개 더 나올 지 모르기 때문에 사이즈를 맞추지 못해도 상관없다는 것이다.

 예를 들어 adeeee라는 문자를 테스트 했을 때에는 6번째 그림에서 target_pointer를 증가시켰으므로 while문을 빠져나와서 true를 return할건지 false를 return할건지 검사해야한다. 이 때 word에서의 포인터는 아직 3이라는 index 위치에 있고 word의 길이는 6이지만 *의 특성상 길이가 상관없기 때문에 true를 반환하게 하는 것이다.

 

정답

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

int idx = 0;
int searchOthers = 0;
int cache[101][101];

bool checkMatching(vector<char>& target, string& word, int tp, int wp) {
    int& ret = cache[tp][wp];
    if (ret != -1) return ret;
     // tp: 현재 target의 몇번째 문자를 검사 중인지
     // wp: 현재 word의 몇번째 문자를 검사 중인지
    while (tp<target.size()&&wp<word.size()&&(target[tp]=='?'||target[tp]==word[wp])) {
        // ?일 때
        // 문자가 서로 같을 때
        // 아직 target과 word 둘 다 끝까지 안봤을 때
        tp++; wp++;
    }
    if (tp == target.size())
        return wp == word.size();
    if (target[tp] == '*') {
        for (int i = 0; i <= word.size() - wp; i++) {
            if (checkMatching(target, word, tp+1, wp+i))
                return true;
        }
    }
    return false;
}

int main() {
    int c;
    cin >> c;
    cin.ignore(256, '\n');

    while (c--) {
        string word_list[50]; // 단어 리스트
        string answer_list[50]; // 정답 리스트
        memset(cache, -1, sizeof(cache));
        idx = 0;

        string w;
        getline(cin, w);

        vector<char> w_arr;
        for (int i = 0; i < w.size(); i++)
            w_arr.push_back(w[i]); // string => arr

        int n;
        cin >> n;
        cin.ignore(256, '\n');

        for (int i = 0; i < n; i++) {
            getline(cin, word_list[i]); // 단어를 받아서
            if (checkMatching(w_arr, word_list[i], 0, 0)) // 매칭되면
                answer_list[idx++] = word_list[i]; // 정답 배열에 넣는다.
        }

        sort(answer_list, answer_list + idx); // 정답 배열을 아스키코드 순서로 배치

        for (int i = 0; i < idx; i++) {
            cout << answer_list[i]<<endl;
        }
    }

}

 기본적으로 생각한 방식은 같은데, 본인은 *뒤에 문자가 왔을 때와 안왔을 때로 나누어 해당 단어에서 문자의 존재 갯수만큼 재귀를 돌렸다.

 정답에서는 *가 왔을 때 바로 재귀함수를 동작시켜 더 간단하게 구현하였다. 또한 메모이제이션도 사용하였다. 기존 코드에서는 왜 오류가 났을까? 반례를 아직 찾지 못했다. (반례가 있다면 댓글 부탁..)