[python] algospot Wildcard 문제풀이

문제

와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 0 글자 이상의 어떤 문자열에도 일치한다고 본다.

예를 들어 와일드 카드 he?p 는 파일명 help 에도, heap 에도 매치되지만, helpp 에는 매치되지 않는다. 와일드 카드 *p* 는 파일명 help 에도, papa 에도 매치되지만, hello 에는 매치되지 않는다.

와일드카드 문자열과 함께 파일명의 집합이 주어질 때, 그 중 매치되는 파일명들을 찾아내는 프로그램을 작성하시오.

 

문제풀이

이 문제에서 핵심은 *이다. 와일드카드 *가 나왔을 때 이 문자가 파일 이름에서 몇개의 문자와 매칭되는지를 알아야 한다.

문제를 푸는 시점 즉, *를 만난 시점에는 이 와일드 카드가 몇개의 문자와 매칭되는지 알 수 없다. 

그러므로 가능한 모든 경우의 수를 모두 만들어보는 방법밖에 없다.

 

와일드 카드 *를 만나면 *가 파일 이름에서 하나의 문자를 의미하는 경우, 두개의 문자를 의미하는 경우 ... n개의 문자를 의미하는 경우까지 남은 문자의 개수 n개 만큼 부분문제가 발생한다.

예를 들어 wild card : "tr*qw" 이고, string : "trqqeettqw" 라면
 *를 마주한 순간 string의 인덱스는 2로 q일 것이다. 이때 *가 몇개의 문자열에 해당하는지 모르니까 다 만들어 본다
 *와 매칭 가능한 문자 '', 'q', 'qq', 'qqe', 'qqee', 'qqeet', 'qqeett', 'qqeettq', 'qqeettqw'이다.

 

wildcard와 string의 문자를 가리키는 인덱스 i와 j를 이용해 값을 하나씩 비교해 나간다.

1. 만약 두 문자가 같다면 통과 ( 두 인덱스 모두 +1 )

2. 만약 두 문자가 다르다면 실패 ( return False )

3. 만약 와일드카드 문자가 '?' 이라면 통과 ( 두 인덱스 모두 +1 )

4. 만약 와일드카드 문자 '*'가 나온다면 반복문을 통해 위에서 말한 부분문제로 쪼갠다.

 

코드

import sys

# 1개
N = int(sys.stdin.readline().rstrip())

def match(w_idx, s_idx) :

    if dp[w_idx][s_idx] :
        return dp[w_idx][s_idx]

    # 두 문자가 같거나, 와일드카드 문자가 ?인 경우
    while w_idx < len_wild and s_idx < len_str and (wild_card[w_idx] == string[s_idx] or wild_card[w_idx] == '?') :
        s_idx += 1
        w_idx += 1

    # 와일드카드 문자가 끝났을 때 입력 문자도 끝난다면 True
    if w_idx == len_wild  :
        dp[w_idx][s_idx] = (s_idx == len_str)
        return dp[w_idx][s_idx]

    # 와일드카드 '*'를 만났을 때
    if wild_card[w_idx] is '*' :

        for i in range(s_idx, len_str+1) :
            # w_idx가 len_wild를 넘어가버리는 상황 (*p*일때 w_ixd+1가 가서 len_wild에 해당하는 값이 다음 인자로 넘어감)
            # 그래서 이 경우에 맞는지 틀리는지는 다음 재귀의 w_idx == len_wild부분에서 판단이 된다.
            # 그렇기에 s_idx도 len_str까지 가는 부분까지 포함시켜 range를 만들었다.

            # 부분 문제로 쪼갠다. i가 s_idx부터 len_str까지 있으니 '*'에 해당하는 크기가 0부터 남은 문자열 전체까지
            if match(w_idx+1, i) :
                dp[w_idx][s_idx] = True
                return True

    dp[w_idx][s_idx] = False
    return False


answer = []

for _ in range(N) :

    wild_card = sys.stdin.readline().rstrip()
    n = int(sys.stdin.readline().rstrip())
    strings = []

    for _ in range(n) :
        strings.append(sys.stdin.readline().rstrip())

    ans = []
    for string in strings :

        len_wild = len(wild_card)
        len_str = len(string)
        dp = [[None for _ in range(110)] for _ in range(110)]
        if match(0,0) :
            ans.append(string)

    answer.extend(sorted(ans))


for str in answer :
    print(str)

 

초기 접근 방식과 오답의 원인

접근하기 어려운 문제였다. 재귀 함수를 어떻게 짜야할 지 감이 안잡혔다.

처음에 문자열을 하나하나 비교해가면서 끝까지 검사해서 한번에 끝내려는 생각을 했다.

그런데 wild card : "t*qw*t" , string : "tqw11111qwt"와 같은 문자열이 나왔을 때 qw가 어디에 위치해야 할 지 찾을 수 없겠다는 생각이 들어 포기했다. 

문제 조건에 맞는 재귀함수를 짜는 연습이 더 필요해보인다. 

 

 

문제점 

algospot 문제에서는 정답이 나오지만 밑에와 같은 케이스에서는 엄청난 시간이 걸린다.

wildcild = a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a
string = aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb

 

또한 내가 이해하기로는 dp가 아닌 완전 탐색으로 보인다.

메모이제이션이 정확이 어느 부분에서 쓰이는지 감이 안잡힌다.

 

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.