와일드 카드

시간 2초, 64MB
input :

• 테스트 케이스의 수 C (1 <= C <= 10)
• 와일드 카드 패턴 W.(알파벳 대소문자, 숫자와 *, ? 만으로 구성)
• 파일명의 수 n(1 <= n <= 50)
• 각 파일명 입력.(알파벳 대소문자, 숫자로 구성)

output :

• 주어진 패턴에 대응되는 파일들의 이름을 알파벳 순서대로 한줄에 하나씩 출력.

조건 :

• 와일드 카드 패턴에 대응 되는 파일 명들을 찾으시오.
• ? 는 어떤 글자와도 대응
• *는 0글자 이상의 어떤 문자열에도 대응.

---

떠올려야 할 것은?

재귀적으로 어떻게 풀것인가. -> 동적계획법 적용

함수의 기능. (패턴의 인덱스 P, 문자열의 인덱스 S)

1. *일 때, [P + 1] 과 [S + 1]을 비교 .
   동일 한 경우. 다음 재귀 함수는 (P + 1, S + 1)
   문자열의 길이보다 클때는 가능 함을 표시.
   동일하지 않으면, 다음 재귀함수는 (P, S + 1)
   문자열의 길이보다 커졌으면 불가능함을 표시.

2. ?일 때, 모두 통과.
   다음 재귀 함수 (P + 1, S + 1)
   마지막 아이템이였다.(P가 마지막 아이템일때.) 가능함을 표시.

3. 현재의 인덱스 P 와 S를 비교.
   동일 한 경우, 다음 재귀 함수는 (P + 1, S + 1)
   문자열의 길이보다 클때는 가능 함을 표시.
   동일하지 않으면 불가능함을 표시.

조건이 너무 많다.....

해답은?

기본적으로 반복을 어떻게 시도 할 것인가.
1. 현재의 인덱스는 W보다 작아야 한다.
2. 현재의 인덱스는 S보다 작아야 한다.
3. W가 '?' 일 때나 W[position] == S[position] 일 때는 그냥 통과해도 된다.

def match(W, S):
	pos = 0
	while pos < len(S) and pos < len(W) and (W[pos] == '?' or W[pos] == S[pos]):
		pos += 1

위의 반복문이 끝나는 총 경우의 수는 아래와 같다.

1. W[position] != S[position]일 때, 대응 실패.
2. W 끝에 도달 : 패턴과 문자열의 길이가 같다면 대응 성공 / 아니면 실패.
3. S 끝에 도달 : 남은 패턴이 전부 *일 때만 대응 성공.
4. W[position]이 *인 경우: 재귀 호출. match(W'pos + 1이후의 문자열./ S'pos + skip이후의 문자열)

def match(W, S):
	pos = 0
	while pos < len(S) and pos < len(W) and (W[pos] == '?' or W[pos] == S[pos]):
		pos += 1
	if pos == len(W):
		return pos == len(S) <-- 이게 True or False를 리턴 하겠구만.
	if W[pos] == '*':
		for skip in range(pos, len(S)):
			if match(W[pos + 1:], S[pos + skip]):
				return True
	return False

그러나 문제. 중복되는 문제가 너무 많다.

'*'에 대응 되는 것이 많을 수록 경우의 수 증가.
중요한 단서가. 입력으로 주어질 수 있는 w와 s의 종류가 제한 되어있다는 것이란다.
-> 뭔 말이냐.
아.. 현재 문자열의 최대 길이는 100 이다.
행에는 W의 부분 문자열들을 열에는 S의 부분 문자열들을 만들어
가능성을 저장 하게 하면 훨 씬 빨 라 진 다는 것.....

cache = [[-1] * 101 for _ in range(101)]
W, S = 입력받은 문자열.

def match(w, s): # w, s 는 문자열들의 인덱스를 가리킨다.
	ret = cache[w][s]
	if ret != -1:
		return ret
	pos = 0
	while s < len(S) and w < len(W) and (W[w] == '?' or W[w] == S[s]):
		w += 1
		s += 1
	if w == len(W):
		return ret = (s == len(S))
	if W[w] == '*':
		for skip in range(s, len(S)):
			if match(W[w + 1:], S[s + skip]):
				return ret = 1
	return ret = 0

이 문제의 시간 복잡도를 더 줄이려면?
While 반복문안의 for문을 없애야 한다.
->>각 문자 하나에 대해 한 번 수행하는 함수를 만드는 것

while s < len(S) and w < len(W) and (W[w] == '?' or W[w] == S[s]):
->> if s < len(S) and w < len(W) and (W[w] == '?' or W[w] == S[s]):

if W[w] == '*':
		for skip in range(s, len(S)):
			if match(W[w + 1:], S[s + skip]):
->>>
if W[w] == '*':
		if (match(w + 1, s) or (s < len(s) or match(w, s + 1))):