[Algospot] 와일드카드 (문제 ID : WILDCARD)

문제

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

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

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

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

 

입력

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

 

출력

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

---

까다롭고 어려운 문제였다. 와일드카드와 입력 받은 문자열을 한 글자씩 비교한다. wildcard 함수에서 와일드카도와 문자열의 위치를 입력값으로 받고, dp배열에도 문자열의 위치에 따라 대응되는지를 저장한다. 두 문자가 같은 문자거나 와일드카드의 문자가 '?'라면 위치를 하나씩 증가해서 호출한다. 문제는 와일드카드의 문자가 '*'일 때인데 와일드카드에 문자열을 몇 글자나 대응시켜야 할지가 관건이기 때문이다. 따라서 *가 나오면 wildcard의 위치만 하나 증가하거나 문자열의 위치만 하나씩 증가하는 방식으로 모든 경우를 조사한다. 모든 경우에 해당하지 않으면 일치하지 않는다는 뜻이기 때문에 0을 반환한다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/WILDCARD.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;
int C, N;
string W, S;
int dp[101][101];

int wildcard(int wpos, int spos)
{
	int &ret = dp[wpos][spos];
	if (ret != -1) return ret;

	if(wpos < W.size() && spos < S.size() &&(W[wpos]=='?' || W[wpos]==S[spos])) 
		return ret = wildcard(wpos + 1, spos + 1);
	if (wpos == W.size() && spos == S.size())
		return ret = 1;
	if (W[wpos] == '*') {
		if (wildcard(wpos + 1, spos) || (spos<S.size() && wildcard(wpos, spos + 1))) {
			return ret = 1;
		}
	}
	return ret = 0;
}
int main()
{
	cin >> C;
	while (C--) {
		cin >> W;
		cin >> N;
		vector<string> v;
		while (N--) {
			cin >> S;
			memset(dp, -1, sizeof(dp));
			if (wildcard(0, 0) == 1) v.push_back(S);
		}
		sort(v.begin(), v.end());
		for (int i = 0; i < v.size(); i++)
			cout << v[i] << "\n";
	}
}