문제
와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 포함한다.
와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 0 글자 이상의 어떤 문자열에도 일치한다고 본다.
예를 들어 와일드 카드 he?p 는 파일명 help 에도, heap 에도 매치되지만, helpp 에는 매치되지 않는다. 와일드 카드 *p* 는 파일명 help 에도, papa 에도 매치되지만, hello 에는 매치되지 않는다.
와일드카드 문자열과 함께 파일명의 집합이 주어질 때, 그 중 매치되는 파일명들을 찾아내는 프로그램을 작성하시오.
입력
입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 10) 가 주어진다. 각 테스트 케이스의 첫 줄에는 와일드카드 문자열 W 가 주어지며, 그 다음 줄에는 파일명의 수 N (1 <= N <= 50) 이 주어진다. 그 후 N 줄에 하나씩 각 파일명이 주어진다. 파일명은 공백 없이 알파벳 대소문자와 숫자만으로 이루어져 있으며, 와일드카드는 그 외에 * 와 ? 를 가질 수 있다. 모든 문자열의 길이는 1 이상 100 이하이다.
출력
각 테스트 케이스마다 주어진 와일드카드에 매치되는 파일들의 이름을 한 줄에 하나씩 아스키 코드 순서(숫자, 대문자, 소문자 순)대로 출력한다.
예제 입력
2 he?p 3 help heap helpp *p* 3 help papa hello
예제 출력
heap help help papa
[접근방식]
- 완전탐색 가능? ⇒ 범위가 작아서 가능할듯(재귀 / for 문)
- 풀이기법 ⇒ 정렬로 풀 경우에 *가 여러자릿수가 된다는 게 문제가 됨 ⇒ 정규식으로는 가능할듯
[풀이코드(정규식)]
import re
#입력값
# wild = 'he?p'
# files = ['help', 'heap', 'helpp']
wild = '*p*'
files = ['help', 'papa', 'hello']
new_wild = ''
for char in wild:
if char == '?':
new_wild += '.'
if char == '*':
new_wild += '.*'
else:
new_wild += char
regExp = re.compile(new_wild)
ans = []
for file in files:
match = re.match(regExp, file)
if match:
#자릿수를 맞춰주기 위해(?만 있을 땐 처음에 길이 확인하면 되지만, *때문에)
if file == match.group():
ans.append(file)
print(ans)
[책 풀이(DP)]
#입력값
# wild = 'he?p'
# files = ['help', 'heap', 'helpp']
wild = '*p*'
files = ['help', 'papa', 'hello']
# wild = '*bb*'
# files = ['babbbc']
cache = [[None]*101 for _ in range(101)]
def matchMemoized(w, s, W, S):
ret = cache[w][s]
if ret: return ret
while s < len(S) and w < len(W) and (W[w] == '?' or W[w] == S[s]):
w += 1
s += 1
if w == len(W):
cache[w][s] = (s == len(S))
return cache[w][s]
if W[w] == '*':
for skip in range(len(S)-s+1):
if matchMemoized(w+1, s+skip, W, S):
ret = True
return ret
ret = False
return ret
ans = []
for file in files:
if matchMemoized(0, 0, wild, file):
ans.append(file)
print(ans)
[책 풀이에서 Cache 없앴을 때(완전탐색)]
#입력값
# wild = 'he?p'
# files = ['help', 'heap', 'helpp']
wild = '*p*'
files = ['help', 'papa', 'hello']
# wild = '*bb*'
# files = ['babbbc']
def matchMemoized(w, s, W, S):
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 (s == len(S))
if W[w] == '*':
for skip in range(len(S)-s+1):
if matchMemoized(w+1, s+skip, W, S):
return True
return False
ans = []
for file in files:
if matchMemoized(0, 0, wild, file):
ans.append(file)
print(ans)
참고 : https://junho-one.tistory.com/13
[느낀점/의문점]
- ‘책 풀이’에서 아래의 부분에서 여러개가 불러져서 가고 또 거기서 *로 끝나면 또 부를거니까 memoization을 적용시킨다고 생각했음
if W[w] == '*':
for skip in range(len(S)-s+1):
if matchMemoized(w+1, s+skip, W, S):
ret = True
return ret
- 그런데, 어차피 w+1로 *을 뛰어넘어서 줄테고 매칭이 안 되면 False를 반환하게 되고 앞서서 for구문에서 skip 적용해서 돌리기 때문에 캐싱을 사용하고 있다기 보다는 완전탐색에 가깝다고 사료됨
- 왜 메모이제이션을 여기서 썼는지 잘 모르겠음. 입력값이 아주 크거나 복잡한 값이 들어올 경우에 메모이제이션을 쓰게되나?
- 문자열 parsing 문제에서는 정규식 만큼 강력한 도구가 없는 것 같음
'알고리즘 문제(Python) > 알고스팟(feat.알고리즘문제해결전략)' 카테고리의 다른 글
| [알고스팟/종만북/DP/DFS] 외발뛰기(Python) (0) | 2022.11.06 |
|---|---|
| [알고스팟/종만북/분할정복/재귀/스위핑] 울타리 잘라내기(Python) (0) | 2022.11.06 |
| [알고스팟/종만북/완전탐색/재귀] 시계 맞추기(Python) (0) | 2022.11.06 |
| [알고스팟/종만북/완전탐색/재귀] 게임판 덮기(Python) (0) | 2022.11.06 |
| [알고스팟/종만북/완전탐색/재귀] 소풍(Python) (0) | 2022.11.06 |
