동적 계획법 - 2. 와일드카드

문제 : 와일드카드 (난이도 中)

 

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

 

 분석

문제를 보면 '*'가 핵심인 것을 알 수 있다.

 

입력 데이터를 input_data, 비교할 이름 데이터를 name_data할 때 다음과 같은 케이스로 나눠 생각해보자.

 

1. input_data[pos] != name_data[pos] : 실패인 경우.

2. input_data가 끝에 도달한 경우 : *가 없이 도달한 경우, name_data길이와 같은 경우 성공.

3. name_data가 끝에 도달한 경우 : input_data에서 남은 data가 모두 *인 경우만 성공. 그외에는 다 실패.

4. input_data가 *인 경우 : *에 몇글자가 대응될지 모르기에 남은 길이를 다시 검사한다. 

 

 구현

bool match(const string& input_data, const string& name_data)
{
	int pos = 0;
	while (pos < input_data.size() && pos < name_data.size() && (input_data[pos] == '?' || input_data[pos] || name_data[pos]))
	{
		++pos;
	}
	//case 2. return 값에 주목하자.
	if (pos == input_data.size())
	{
		return pos == name_data.size();
	}
	//case 4.
	if (input_data[pos] == '*')
	{
		for (int skip = 0; skip < input_data.size(); skip++)
		{
			if (match(input_data.substr(pos + 1), name_data.substr(pos + skip)))
			{
				return true;
			}
		}
	}
	return false;
}

 

 최적화

패턴 "*****a"와 "aaaaaaaaaaaaaaab" 같은 경우 수많은 경우의 수를 검사하는 것을 알 수 있다.

따라서 메모이제이션 과정을 통해 최적화를 해야한다.

 

int cache[101][101];
string input_data, name_data;
bool match(int w, int s)
{
	//memoization
	int& ret = cache[w][s];
	if (ret != -1) return ret;
	//input_data[input_data]와 name_data[s]를 맞춰간다.
	if (w < input_data.size() && s < name_data.size() && (input_data[w] == '?' || input_data[w] == name_data[s]))
	{
		return ret = match(w + 1, s + 1);
	}
	//case 2.
	if (w == input_data.size())
	{
		return ret = (s == name_data.size());
	}
	//case 4.
	if (input_data[w] == '*')
	{
		if (match(w + 1, s) || (s < name_data.size() && match(w, s + 1)))
		{
			return ret = 1;
		}
	}
	//case 3.
	return ret = 0;
}