Algorithm/종만북

WILDCARD (DP)

ChoiSW 2025. 2. 22. 18:13

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

 

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

using namespace std;

// Match 함수의 while 종료 조건
//	1. pos == wildcard.size() 
//		와일드카드가 끝에 도달했을 때, 파일명도 끝에 도달했으면 true /파일명은 끝에 도달 못했으면 false
//	2. pos == filename.size()
//		파일명의 끝에 도달했으면, 
//			1번을 먼저 처리했기에 filename은 끝이고 wildcard는 끝이 아니기에 무조건 false라고 생각했다. 
//			하지만, wildcard[pos]가 * 가 아닌 경우에만 false 이다.
// 
//	3. wildcard[pos] != '?' && wildcard[pos] != filename[pos]
//		?가 아니고 둘이 다를 때, 
//		wildcard[pos] == '*'일 때를 확인해야한다.	
//
//	
// 

bool Match(string wildcard, string filename)
{
	int pos = 0;
	// 와일드카드와 파일명의 끝이 아니고 ( ?거나 문자가 같으면 ) pos++
	while (pos < wildcard.size() && pos < filename.size() &&
		(wildcard[pos] == '?' || wildcard[pos] == filename[pos]))
		pos++;

	// while 종료 조건 확인
	// 1. pos == wildcard.size() 
	if (pos == wildcard.size())
		*return pos == filename.size();
	else
	{
		// 2. pos == filename.size()
		if (wildcard[pos] != '*' && pos == filename.size())
			return false;
	}

	if (wildcard[pos] == '*')
	{
		for (int skip = 0; pos + skip <= filename.size(); skip++)
		{
			// wildcard 의 *다음에 대해서
			// filename 의 pos부터 끝까지 획인
			if (Match(wildcard.substr(pos + 1), filename.substr(pos + skip)))
				return true;
		}
	}*

	return false;
}

int main()
{
	int C; cin >> C;

	while (C-- > 0)
	{
		vector<string> matched;

		string wildcard; cin >> wildcard;
		int n; cin >> n;

		while (n-- > 0)
		{
			string filename; cin >> filename;

			if (Match(wildcard, filename))
				matched.push_back(filename);

		}

		sort(matched.begin(), matched.end());

		for (string w : matched)
			cout << w << "\\n";
	}
}

 

아래의 else 부분은 그 아래의 if(wildcard[pos] == ‘*’) 처리로 인해 걸러질 수 있기에 없어도 되는 부분이다.

bool Match(string wildcard, string filename)
{
	int pos = 0;
	while (pos < wildcard.size() && pos < filename.size() &&
		(wildcard[pos] == '?' || wildcard[pos] == filename[pos]))
		pos++;

	if (pos == wildcard.size())
		*return pos == filename.size();
	else
	{
		if (wildcard[pos] != '*' && pos == filename.size())
			return false;
	}

	if (wildcard[pos] == '*')
	{
		for (int skip = 0; pos + skip <= filename.size(); skip++)
		{
			// wildcard 의 *다음에 대해서
			// filename 의 pos부터 끝까지 획인
			if (Match(wildcard.substr(pos + 1), filename.substr(pos + skip)))
				return true;
		}
	}*
	
	return false;
}

위의 풀이에서는 중복되는 부분문제가 있다.

wildcard = "*a*b*c"이고 filename = "aaabbc"인 경우

Match(*a*b*c, aaabbc) 에서 wildcard의 맨앞에 *이 나왔으므로, skip = 0부터 쭉 다 확인한다.

Match(a*b*c, aaabbc), Match(a*b*c, aabbc), Match(a*b*c, abbc) , Match(a*b*c, bbc), … 경우를 확인한다.

  1. (abc, aaabbc) 맨앞 a은 while문에 의해 넘어가지고(pos++) 그 다음은 *이기에 skip = 0부터 다 확인한다.
    1. (b*c, aabbc)
    2. … 모든 경우를 확인한다.
    3. (b*c, abbc)
    4. … 모든 경우를 확인한다.
    5. (b*c, bbc)
    6. … 모든 경우를 확인한다.
    7. (b*c, bc)
    8. … 모든 경우를 확인한다.
    9. (b*c, c)
    10. … 모든 경우를 확인한다.
    11. (b*c, )
  2. (abc, aabbc) 맨앞 a은 while문에 의해 넘어가지고(pos++) 그 다음은 *이기에 skip = 0부터 쭉 다 확인한다.
    1. (b*c, abbc)
    2. … 모든 경우를 확인한다.
    3. (b*c, bbc) → 중복 발생!!
    4. … 모든 경우를 확인한다.
    5. (b*c, bc)
    6. …
    7. (b*c, c)
    8. …
  3. (abc, abbc) …
  4. (abc, bbc) …

…

 

* 는 filename의 모든 부분에 대해 부분집합을 만들 수 있다. -> 중복 발생

예를 들어, "***"는 "abc"에 대해 다음과 같이 모든 경우를 고려해야 한다.

"", "a", "b", "c", "ab", "ac", "bc", "abc" // 2^3 = 8개
  • 즉, 길이가 N인 문자열에 대해 *가 N개 있으면, 모든 부분집합을 탐색하는 것과 동일
  • 부분집합의 개수 = 2^N
  • 따라서, 100개의 ``가 있으면 최악의 경우 2^100개의 상태를 고려해야 함

이는 101 x 101 = 10201 개의 캐시를 넘어가기에 중복되는 부분문제가 발생하게 된다!!

중복되는 부분 문제 → 메모이제이션 적용

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // fill, sort
#include <cstring> // memset

using namespace std;

// while 종료 조건
//	1. pos == wildcard.size() 
//		와일드카드가 끝에 도달했을 때, 파일명도 끝에 도달했으면 true 
//									 파일명은 끝에 도달 못했으면 false
//	2. pos == filename.size()
//		파일명의 끝에 도달했으면, 
//			1번을 먼저 처리했기에 filename은 끝이고 wildcard는 끝이 아니기에 무조건 false라고 생각했다. 
//			하지만, wildcard[pos]가 * 가 아닌 경우에만 false 이다.
// 
//	3. wildcard[pos] != '?' && wildcard[pos] != filename[pos]
//		?가 아니고 둘이 다를 때, 
//		wildcard[pos] == '*'일 때를 확인해야한다.	
//

// -1아직계산안함 / 0 계산했고 Match실패 / 1 계산했고 Match 성공
int Cached[101][101];

string wildcard;
string filename;

bool Match(int wc, int fn)
{
	int& ret = Cached[wc][fn];
	if (ret != -1)	return ret;

	// 와일드카드와 파일명의 끝이 아니고 ( ?거나 문자가 같으면 ) pos++
	while (wc < wildcard.size() && fn < filename.size() &&
		(wildcard[wc] == '?' || wildcard[wc] == filename[fn]))
	{
		wc++;
		fn++;
	}

	// 와일드카드 끝
	if (wc == wildcard.size())
		return ret = (fn == filename.size());

	if (wildcard[wc] == '*')
	{
		for (; fn <= filename.size(); fn++)
		{
			// wildcard 의 *다음에 대해서
			// filename 의 pos부터 끝까지 획인
			if (Match(wc + 1, fn))
				return ret = 1;
		}
	}

	return ret = 0;
}

int main()
{
	int C; cin >> C;

	while (C-- > 0)
	{

		vector<string> matched;

		cin >> wildcard;
		int n; cin >> n;

		while (n-- > 0)
		{
			cin >> filename;
			
			// fill(&Cached[0][0], &Cached[100][101], -1);
			memset(Cached, -1, sizeof(Cached));

			if (Match(0, 0))
				matched.push_back(filename);
		}

		sort(matched.begin(), matched.end());

		for (string w : matched)
			cout << w << "\\n";
	}
}

 

fill(&Cached[0][0], &Cached[100][101], -1); 에서 [인덱스-1][인덱스]로 해줘야함!

현재 시간복잡도는 O(n^3)이다.

 

아래의 방법을 통해 O(n^2) 시간복잡도로 풀 수 있다.

1차원 반복문을 재귀함수로 바꿔준다!

  1. Match함수의 while문을 통해 wc++; fn++; 해주는 부분을 다음과 같이 수정한다.
	// 와일드카드와 파일명의 끝이 아니고 ?거나 문자가 같으면
	if (wc < wildcard.size() && fn < filename.size() &&
		(wildcard[wc] == '?' || wildcard[wc] == filename[fn]))
	{
		// 다음 글자부터 확인한다.
		return ret = Match(wc + 1, fn + 1);
	}
  1. *에 몇글자가 대응되어야 할지 확인하는 반복문을 다음과 같이 수정한다.
	if (wildcard[wc] == '*')
	{
		// *에 0글자 대응과 1글자 대응 모두 고려
		if ( Match(wc + 1, fn) || 
			fn < filename.size() && Match(wc, fn+1) )
			return ret = 1;
	}

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring> // memset

using namespace std;

// -1아직계산안함 / 0 계산했고 Match실패 / 1 계산했고 Match 성공
int Cached[101][101];
string wildcard;
string filename;

bool Match(int wc, int fn)
{
	int& ret = Cached[wc][fn];
	if (ret != -1)	return ret;

	// 와일드카드와 파일명의 끝이 아니고 ?거나 문자가 같으면
	if (wc < wildcard.size() && fn < filename.size() &&
		(wildcard[wc] == '?' || wildcard[wc] == filename[fn]))
	{
		// 다음 글자부터 확인한다.
		return ret = Match(wc + 1, fn + 1);
	}

	// 와일드카드 끝
	if (wc == wildcard.size())
		return ret = (fn == filename.size());

	if (wildcard[wc] == '*')
	{
		// *에 0글자 대응과 1글자 대응 모두 고려
		if ( Match(wc + 1, fn) || 
			fn < filename.size() && Match(wc, fn+1) )
			return ret = 1;
	}

	return ret = 0;
}

int main()
{
	int C; cin >> C;

	while (C-- > 0)
	{

		vector<string> matched;

		cin >> wildcard;
		int n; cin >> n;

		while (n-- > 0)
		{
			cin >> filename;
			
			//fill(&Cached[0][0], &Cached[100][101], -1);
			memset(Cached, -1, sizeof(Cached));

			if (Match(0, 0))
				matched.push_back(filename);

		}

		sort(matched.begin(), matched.end());

		for (string w : matched)
			cout << w << "\\n";
	}
}