Welcome to My IT World

문제

와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 포함한다.

와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 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

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

[접근방식]

1. 완전탐색 가능? ⇒ 범위가 작아서 가능할듯(재귀 / for 문)
2. 풀이기법 ⇒ 정렬로 풀 경우에 *가 여러자릿수가 된다는 게 문제가 됨 ⇒ 정규식으로는 가능할듯

[풀이코드(정규식)]

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

[느낀점/의문점]

1. ‘책 풀이’에서 아래의 부분에서 여러개가 불러져서 가고 또 거기서 *로 끝나면 또 부를거니까 memoization을 적용시킨다고 생각했음

if W[w] == '*':
    for skip in range(len(S)-s+1):
        if matchMemoized(w+1, s+skip, W, S):
            ret = True
            return ret

1. 그런데, 어차피 w+1로 *을 뛰어넘어서 줄테고 매칭이 안 되면 False를 반환하게 되고 앞서서 for구문에서 skip 적용해서 돌리기 때문에 캐싱을 사용하고 있다기 보다는 완전탐색에 가깝다고 사료됨
2. 왜 메모이제이션을 여기서 썼는지 잘 모르겠음. 입력값이 아주 크거나 복잡한 값이 들어올 경우에 메모이제이션을 쓰게되나?
3. 문자열 parsing 문제에서는 정규식 만큼 강력한 도구가 없는 것 같음