[AlgoSpot] 알고스팟 > WILDCARD(와일드카드) - Python 문제풀이 👀

<알고스팟 문제풀이>

---

해답)

import sys


def readline():
    return sys.stdin.readline()


def solution(w_str, i_strs):
    answer = []
    for i_str in i_strs:
        if isMatched(w_str, i_str):
            answer.append(i_str)
    for answerStr in sorted(answer):
        print(answerStr)
    return 0


def isMatched(w_str, i_str):
    if len(i_str) == 0 and len(w_str) == 0:
        return True
    if len(w_str) == 0:
        return False
    if w_str[0] == '*':
        if len(i_str) == 0:
            return isMatched(w_str[1:], i_str)
        return isMatched(w_str[1:], i_str) or isMatched(w_str, i_str[1:])
    if len(i_str) == 0 or len(w_str) == 0:
        return False
    if w_str[0] == '?':
        return isMatched(w_str[1:], i_str[1:])
    if w_str[0] != i_str[0]:
        return False
    return isMatched(w_str[1:], i_str[1:])


ProblemCount = int(readline())

for _ in range(ProblemCount):
    w_str = readline()  # 와일드카드 문자열
    i_strs = []  # 비교할 문자열들
    i_str_Count = int(readline())
    for _ in range(i_str_Count):
        i_strs.append(readline())
    solution(w_str, i_strs)

 

* 문제및 로고의 저작권은 알고스팟에 있습니다.

 

풀이)

 와일드카드 문자열(w_str) 과 입력받은 문자열(i_str)을 비교하며

 

0. 두 문자열이 모두 길이가 0인 경우 - 합당한 문자열이다. (종료 조건!)

 

1. 첫번째 인덱스의 문자를 비교한다.

2. 두 문자가 같을경우 - 두 문자열 모두 다음 인덱스로 넘어간다. (다음 문자 검사)

3. 두 문자가 다를경우(*과 ?이 아니고) - 올바르지않은 문자열이다. (종료)

재귀함수를 통해 이 과정을 거치다가 두 문자열이 모두 길이가 0인 경우 - 합당한 문자열이다. (종료)

 

문제는 *과 ? 일 때 이다!

• ? 일때 : 어떤 문자와도 매칭이 가능하므로 두 문자열 모두 다음 인덱스로 넘어간다.
• * 일때 : *은 여러 문자와도 매칭이 될 수 있기에 *을 지우지않고 인풋 문자열만을 지운 다음 인덱스 or 
• * 일때2 : *은 문자가 오지가 않은것에도 매칭이 될수 있기에 *을 지우고 인풋문자열은 그대로인 그대로 인덱스

이렇게 재귀를 통해 탐색한다. 

---

- 추가사항

• *이 많아지면 시간이 오래걸리므로 동적으로 캐싱을 도입하는 것도 좋아보인다.
• 반복된 *은 *하나로 대체해도 된다.