알고스팟_ 와일드 카드_ 종만북_DP

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

algospot.com :: WILDCARD

 풀이방법

 1. * 는 0 글자 이상의 어떤 문자열에도 일치한다고 본다.

 2. ? 는 어떤 글자와 비교해도 일치한다고 본다.

 

 이 문제는 주어진 두 조건중에 1번이 매우 중요한 문제다.

 

 일단 이런 까다로운 문제를 만날때 먼저 할수있는것이 완전탐색 방법이다.

 

 완전탐색

 아이디어 : 주어진 와일드 카드가 m개의 *를 가지고 있다고 할때, *가 나올때마다 *가 몇개의 문자열에 대응될것인가를 모두 탐색을 해주자.

 

 ex) 와일드카드 : he*p, 비교할카드 : help 일때

 *가 0글자일때, *가 1글자일때, *가 2글자일때를 다 substr을 이용해 잘라서 재귀함수에 넣고 완전탐색한다.

 여기서는 match ("p", "lp"), match("p", "p"), match("p", "") 세가지의 경우를 알아볼것이다.

 

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;
}

 하지만, 이렇게 푼다면

 와일드카드 : *********a, 비교할카드 : aaaaaaaaaab 이런 문제가 있을때,

 어짜피 와일드카드와 비교할카드의 끝이 달라 서로 대응될수없지만 완전탐색이므로 앞에서부터 모든 경우의 수를 살펴볼것이다.

 시간도 최대 100글자이므로 *로 꽉찬 와일드카드라면 아마 시간을 많이 잡아먹을것이다. 그러므로 이제 한번 시간을 줄여보자.

 

 메모제이션 활용

 메모제이션으로 이 상황을 해결할 수 있다. 위의 완전탐색은 중복되는 계산이 아주 많다. 그러므로 int cache[와일드카드의 시작점][비교할카드의 시작점]을 만들어 -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]를 맞춰나간다
	while (s < S.size() && w < W.size() && (W[w] == '?' || W[w] == S[s]))
	{
		++w;
		++s;
	}
	//더 이상 대응할수 없으면 왜 while문이 끝났는지 확인한다.
	//2. 패턴 끝에 도달해서 끝난 경우 : 문자열도 끝났어야 참
	if (w == W.size()) 
		return ret = (s == S.size());

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

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

 코드를 보면 완전탐색과 거의 동일하지만 총 두가지가 바뀌었다

1. 인자가 int로 바뀌어 각각의 시작점을 저장하는점. 

2. cache에 이미 계산이 되어 있다면 바로 값을 return하여 중복되는 계산을 막은점.

 

 이렇게 풀면 시간복잡도는 와일드카드와 비교할카드의 문자열의 길이가 둘다 n이면 부분문제는 n^2이고, 재귀호출을 최대 n번하므로 O(n^3)이다. 주어진 n<=100이면 약1'000'000번의 계산밖에 안하므로 시간은 충분하다.

 

 시간을 더더더 줄이는 방법

 위의 O(n^3)에서 시간을 더욱 줄이는 방법이 있다. 분해방식을 조금 고치면 되는데

//W[w]와 S[s]를 맞춰나간다
while (s < S.size() && w < W.size() && (W[w] == '?' || W[w] == S[s]))
{
	++w;
	++s;
}
...
if (W[w] == '*')
	for (int skip = 0; skip + s <= S.size(); ++skip)
		if (matchMemoized(w + 1, s + skip))
			return ret = 1;

 위의 반복문 구문을 밑처럼 바꾸면 메모제이션을 더욱 효과적으로 쓸수있다.

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

 시간은 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;
}

---

 후기

 종만북 dp에서 왜 막힌다고 하는지 슬슬 느끼는 중이다. 이 문제 이해하려고 이 코드만 3시간 봤다 ㅋㅋㅋㅋ

 

 혹시 틀린부분이나 이상하게 문장을 쓴 부분이 있다면 말해주세요. ㅎ