[ALGOSPOT] WILDCARD

출처: algospot.com/judge/problem/read/WILDCARD

algospot.com :: 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

 

 

그렇다... 나만 당한게 아니라 다들 당했었다..

댓글을 보니 sorting 안하고 맞왜틀인 사람이 많았다.

 

<아이디어>

와일드카드 문자열과 파일명을 비교하는데, 기본적으로 1칸씩 비교한다.

와일드카드 문자열에 '?'가 등장하면 묻지도 따지지도 않고 다음 칸으로 이동한다.

와일드카드 문자열과 파일명의 해당 위치의 글자가 같은 경우 또한 다음 칸으로 이동한다.

만약 둘 다 맨 마지막까지 탐색했다면 true를 return 한다.

 

가장 중요한건 '*'이 등장했을 때이다. 책에서도 '*'이 등장하는 부분을 중요하게 여겼다.

'*'은 0글자 이상의 어떤 문자열과도 일치한다고 보니, '*'이 연속적으로 있으면 의미 없다.

그래서 while로 넘어가줬다. 이때 '*'이 마지막 문자이면 그냥 true를 return 한다.

파일명에 어떤 문자들이 와도 와일드카드 문자열에서 '*'이 마지막 문자열이면 그 다음 문자열에는 그냥 무적이다.

 

'*'이 마지막이 아니면 다음문자로 가서 다시 비교해주면 된다.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
bool check(string& cmd, string& cmp, size_t cmd_pos, size_t cmp_pos)
{
    bool ret = false;
    if(cmd_pos==cmd.length() && cmp_pos==cmp.length()) return true;
    if(cmd_pos<cmd.length() && cmp_pos<cmp.length())
    {
        if(cmd[cmd_pos]=='?') return ret |= check(cmd, cmp, cmd_pos+1, cmp_pos+1);
        if(cmd[cmd_pos]==cmp[cmp_pos]) return ret |= check(cmd, cmp, cmd_pos+1, cmp_pos+1);
    }
 
    if(cmd[cmd_pos]=='*')
    {
        while(cmd[cmd_pos]=='*')
        {
            cmd_pos++;
            if(cmd_pos==cmd.length()) return true;
        }
        while(cmp_pos<cmp.length())
        {
            ret |= check(cmd, cmp, cmd_pos, cmp_pos);
            cmp_pos++;
        }
    }
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int tc;
    cin>>tc;
    while(tc--)
    {
        string cmd, cmp;
        cin>>cmd;
        int n;
        cin>>n;
        vector<string> v;
        for(int i=0;i<n;i++)
        {
            cin>>cmp;
            if(check(cmd, cmp, 0, 0)) v.push_back(cmp);
        }
        sort(v.begin(), v.end());
        for(size_t i=0;i<v.size();i++)
            cout<<v[i]<<endl;
    }
    return 0;
}