WILDCARD

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

using namespace std;

const int MAX_BUFFER_SIZE = 1024;
const int MAX_TEXT_LENGTH = 100;
char input[MAX_BUFFER_SIZE];

string src, dest;
int cache[MAX_TEXT_LENGTH][MAX_TEXT_LENGTH] = {-1, };
vector<string> results;

bool IsMatched(int srcIdx, int destIdx);

int main()
{
	int caseNum = 0;

	cin >> caseNum;

	cin.ignore();
	for (int cIter = 0; cIter < caseNum; cIter++)
	{
		// initialize
		src = "";

		// input
		cin.getline(input, MAX_BUFFER_SIZE);
		src = string(input);

		int itemNum = 0;
		cin >> itemNum;

		cin.ignore();
		for (int i = 0; i < itemNum; i++)
		{
			cin.getline(input, MAX_BUFFER_SIZE);
			dest = string(input);

			// initialize
			for (int i = 0; i < MAX_TEXT_LENGTH; i++)
				for (int j = 0; j < MAX_TEXT_LENGTH; j++)
					cache[i][j] = -1;

			if (IsMatched(0, 0) == 1)
			{
				results.push_back(dest);
			}
		}
	}

	sort(results.begin(), results.end(), greater<string>());
	for (auto result : results)
	{
		cout << result << endl;
	}
}

bool IsMatched(int srcIdx, int destIdx)
{
	int& ret = cache[srcIdx][destIdx];
	if (ret != -1) return ret;

	if (srcIdx == src.length() && destIdx == dest.length()) ret = 1;
	else if (srcIdx == src.length()) ret = 0;
	else if (destIdx == dest.length())
	{
		if (src[srcIdx] == '*') ret = IsMatched(srcIdx + 1, destIdx);
		else ret = 0;
	}
	else if (src[srcIdx] == dest[destIdx]) ret = IsMatched(srcIdx + 1, destIdx + 1);
	else if (src[srcIdx] == '?') ret = IsMatched(srcIdx + 1, destIdx + 1);
	else if (src[srcIdx] == '*')
	{
		ret = IsMatched(srcIdx, destIdx + 1);
		if (ret == 0) ret = IsMatched(srcIdx + 1, destIdx + 1);
	}
	else
	{
		if (src[srcIdx] == dest[destIdx]) ret = 1;
		else ret = 0;
	}

	return ret;
}

IsMatched() 함수의 주요 로직은 금방 짰는데, 기저 사례 처리에서 애를 많이 먹었다. 

else if (srcIdx == src.length()) ret = 0;
else if (destIdx == dest.length())
{
	if (src[srcIdx] == '*') ret = IsMatched(srcIdx + 1, destIdx);
	else ret = 0;
}

위의 코드를 

else if (srcIdx == src.length() || destIdx == dest.length()) ret = 0;

라고 써놓아서  *p*  와  help  의 비교가 false 로 나왔기 때문이다.

destIdx 가 dest.length() 에 도달했더라도, src[srcIdx] 가 * 라면 src 를 더 탐색해야 하는데 더 이상 진행하지 않고 그냥 ret == 0 을 반환했던 것이었다.

그리고 아래는 종만북에 나온 솔루션이다. 내가 짠 코드보다 훨씬 깔끔하다 ㅠ

나는 src 와 dest 둘 모두의 관점에서 코딩을 하였지만, 종만북은 src 의 관점에서 코드를 짰다. 그래서 한 쪽만 고려하면 되었기 때문에 훨씬 코드가 깔끔한 것 같다.

bool IsMatched(int srcIdx, int destIdx)
{
	int& ret = cache[srcIdx][destIdx];
	if (ret != -1) return ret;

	ret = 0;

	if (srcIdx < src.length() && destIdx < dest.length() &&
		(src[srcIdx] == '?' || src[srcIdx] == dest[destIdx]))
		ret = IsMatched(srcIdx + 1, destIdx + 1);
	if (srcIdx == src.length()) ret = (destIdx == dest.length() ? 1 : 0);
	if (src[srcIdx] == '*')
	{
		if (IsMatched(srcIdx + 1, destIdx) == 1 ||
			(destIdx < dest.length() && IsMatched(srcIdx, destIdx + 1) == 1))
			ret = 1;
	}

	return ret;
}

WildcardInput.txt

WildcardOutput.txt