[종만북 문제] 와일드카드 (문제 ID : WILDCARD, 난이도 : 중)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. DP 문제는 중복 계산되는 것이 무엇인지 체크하는 것이 중요하다.

[종만북 문제] 와일드카드 (문제 ID : WILDCARD, 난이도 : 중)

일단 DP 를 이용해서 한 번 풀어보았다. 부끄럽지만 나는 처음에 이렇게 풀었다 :

#include <iostream>
#include "stdlib.h"
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

/****************************************************************************************************/

// length of pattern and word
int P;
int W;

char pattern[100];
char word[100];

int cache[100][100];

int findMatch(int p, int w)
{
	// 기저 조건
	if (p == P && w == W)
		return 1;
	if (p == P && w != W)
		return 0;
	if (p != P && w == W)
	{
		// word 의 마지막에 도달했는데, pattern 의 나머지 문자가 전부 '*' 일 경우
		bool allStar = true;
		while (p < P)
		{
			if (pattern[p++] != '*')
			{
				allStar = false;
				break;
			}
		}

		return (allStar ? 1 : 0);
	}

	// 캐싱 정보 활용
	if (cache[p][w] != -1)
		return cache[p][w];

	bool match = false;
	if (pattern[p] == '*')
	{
		// '*' 가 체크할 갯수를 정하면서, 하나만 매칭이 성공해도 매칭으로 판단
		for (int i = w; i <= W; ++i)
		{
			match = (match || (findMatch(p + 1, i) == 1 ? true : false));
			if (match)
				break;
		}
	}
	else if (pattern[p] == '?')
	{
		match = findMatch(p + 1, w + 1);
	}
	else
	{
		if (pattern[p] == word[w])
			match = findMatch(p + 1, w + 1);
	}

	// 캐싱
	if (match)
		cache[p][w] = 1;
	else
		cache[p][w] = 0;

	return cache[p][w];
}

void sol()
{
	string ps;
	cin >> ps;

	P = ps.size();
	for (int i = 0; i < P; ++i)
		pattern[i] = ps[i];

	int N;
	cin >> N;

	vector<string> ans;
	for (int i = 0; i < N; ++i)
	{
		string ws;
		cin >> ws;
	
		W = ws.size();

		for (int p = 0; p < P; ++p)
			for (int w = 0; w < W; ++w)
				cache[p][w] = -1;

		for (int w = 0; w < W; ++w)
			word[w] = ws[w];

		if (findMatch(0, 0) == 1)
			ans.push_back(ws);
	}
	sort(ans.begin(), ans.end());
	for (auto& s : ans)
		cout << s << endl;
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		sol();
	}

	return 0;
}

위 코드는 패턴과 단어의 index 를 높여나가면서, 매칭된 결과를 캐싱한다. ' * ', ' ? ' 각각에 대해 케이스 처리만 잘 해주면, 통과를 할 수 있다. 😊

 

이제 책에서의 풀이를 한 번 보자. 먼저, 책에서는 완전 탐색 방법으로 푸는 접근법이 먼저 나온다.

 

그런데 중복되는 연산을 바꾸면, 아래와 같이 O(n^3) 으로 풀 수 있다.

 

그런데 사실 내부적으로 루프를 도는 케이스를 없애면, O(n^2) 로도 해결할 수 있다. 아래 코드를 보자(타 블로그에서 참고함).

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

using namespace std;

//bool match(const string& w, const string& s)
//{
//	int pos = 0;
//	while (pos < s.size() && pos < w.size() && (w[pos] == '?' || w[pos] == s[pos]))
//		++pos;
//	//더 이상 대응할 수 없으면 왜 while문이 끝났는지 확인한다.
//	//2. 패턴 끝에 도달해서 끝난 경우 : 문자열도 끝났어야 대응됨
//	if (pos == w.size())
//		return pos == s.size();
//	//4. *를 만나서 끝난 경우 : *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인한다.
//	if (w[pos] == '*')
//		for (int skip = 0; pos + skip <= s.size(); skip++)
//			if (match(w.substr(pos + 1), s.substr(pos + skip)))
//				return true;
//	//이 외의 경우에는 모두 대응되지 않는다
//	return false;
//}

//-1 아직 확인안함
//0 match안됨
//1 match됨
int cache[101][101];
string W, S;

bool matchMemoized(int w, int s)
{
	int& ret = cache[w][s];
	if (ret != -1)	return ret;
	//W[w]와 S[s]를 맞춰나간다
	if (s < S.size() && w < W.size() && (W[w] == '?' || W[w] == S[s]))
	{
		return ret = matchMemoized(w + 1, s + 1);
	}
	//더 이상 대응할수 없으면 왜 while문이 끝났는지 확인한다.
	//2. 패턴 끝에 도달해서 끝난 경우 : 문자열도 끝났어야 참
	if (w == W.size()) 
		return ret = (s == S.size());

	//4. *를 만나서 끝난 경우 : *에 몇글자를 대응해야 할지 재귀 호출하면서 확인
	if (W[w] == '*')
		if (matchMemoized(w + 1, s ) || (s < S.size() && matchMemoized(w, s+1)))
			return ret = 1;

	//3. 이외의 경우에는 모두 대응되지 않는다.
	return false;
}

void cacheInit(int n)
{
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			cache[i][j] = -1;
}

void solve()
{
	int c;
	cin >> c;
	for (int i = 0; i < c; i++)
	{
		vector<string> sucessCards;
		cin >> W;

		int n;
		cin >> n;
		for (int j = 0; j < n; j++)
		{
			//cache init
			cacheInit(100);
			cin >> S;
			//solve ㄱㄱ
			if (matchMemoized(0, 0) == true)
				sucessCards.push_back(S);
		}

		sort(begin(sucessCards), end(sucessCards));
		for (auto& ele : sucessCards)
			cout << ele << endl;
	}
}

int main()
{
	solve();
	return 0;
}

... 극한의 효율충이 되어 보자.