알고스팟: WILDCARD Python 풀이. (동적 계획법 연습문제)

알고스팟의 문제 링크: https://www.algospot.com/judge/problem/read/WILDCARD

문제 와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 포함한다. 와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 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

---

아이디어 및 풀이법 (알고리즘 문제해결 전략으로 부터)

 

2개의 문자열로 입력되는 W와 S의 일치여부를 확인하는 함수 match_prime를 사용하자.

W는 와일드카드의 문자열 1개이고, S는 파일명의 문자열 1개이다.

 

match_prime 함수 내부에 101 X 101 cache 배열이 존재한다.

이 배열은 입력으로 받은 2개의 문자열에서 서브문자열이 시작되는 문자열 상의 위치 인덱스에 따라 각 서브문자열(각 문자열의 접미사라고 생각하면 쉬움.)의 매치여부를 저장하는 배열이다. 

 

말이 어렵다.

 

match_prime[w][s] == 1이라면, W[w:]와 S[s:]가 와일드카드 규칙에 따라 match된다는 것이고, (1을 True의 의미로 삼자. 매치되지 않는 경우는 0, 아직 확인되지 않은 경우는 -1로 둔다.)

 

 

소문자 w, s는 match함수의 입력이다.

match함수는 match_prime함수 내부에서 선언되고 실행된다.

match함수는 w와 s를 입력으로 받아 w와 s의 위치에서 시작하는 서브문자열(각 문자열의 접미사라고 생각하면 쉬움.)의 매치여부를 판단하여 cache에 0혹은 1을 반환한다. 동적계획법의 memoiazion에 따라, 만약 매치여부를 이미 판단했었다면(cache[w][s] != -1이라면) 저장된 값을 바로 반환하여 불필요한 중복을 없앤다.

 

동적계획법의 개념은 아래 링크 참고.

https://studies-choi.tistory.com/33

 

match함수의 코드는 아래와 같다.

    def match(w, s): # w는 wildcard pattern, s는 filename.
        if cache[w][s] != -1: # 이것이 memoization.(한 번 들어왔던 입력이면 저장되어 있는 것 바로 출력.)
            return cache[w][s] # 항체같은 것.
        # 인덱스를 하나하나 이동시키며 일치여부를 확인한다. 
        # w의 원소에 ?가 있으면 일치한다고 판단한다.
        # w의 원소에 *이 나오면 거기서부터 끝까지의 새로운 w', s'를 만들어서 재귀로 넘긴다.
        pos = 0
        while (pos < len(w_prime) - w) and (pos < len(s_prime) - s) and (w_prime[w+pos] == '?' or w_prime[w+pos] == s_prime[s+pos]):
            pos += 1

        # 2가지만 확인하고, 나머지는 모두 False를 반환하면 된다.
        # 우선, 패턴의 끝에 도달해서 끝난 경우, 문자열도 함께 끝났는지 확인하고, 문자열도 끝났다면 True.
        # 패턴의 끝에 도달하지 않았는데, while문이 끝났으면 '*'을 만난 경우이다.
        # 패턴의 마지막 char이 '*'이라면 s의 몇 글자가 이 '*'에 대응해야할지 재귀호출을 통해 찾는다.
        # 몇 글자가 대응했는지는 skip이라는 정수형 변수에 입력한다.

        # 1. s가 끝났는데, w도 마침 끝이다. (일치하는 케이스)
        if pos == (len(w_prime) - w) and pos == (len(s_prime) - s):
            cache[w][s] = 1
            return 1 # 1이 True를 의미한다.
        # 2. s가 안끝났다면 이건 '*'을 만난 상황이다. return 이후이므로 elif나 else가 필요 없다.
        if w_prime[w+pos] == '*':
            skip = 0
            while s + pos + skip < len(s_prime):
                if match(w + pos + 1, s + pos + skip) == 1:
                    cache[w][s] = 1
                    return 1
                skip += 1
        # 나머지의 경우는 모두 False를 의미하는 0을 반환시킨다.
        cache[w][s] = 0
        return 0

부가설명:

구체적인 match함수의 반환조건은 조금 복잡하다.

간단하게 설명하면 매치하려면 2가지 경우의 수 중에 하나이다.

 

첫번째 if문

1. 우선 와일드카드 서브문자열의 끝에 도달했는데 동시에 파일이름의 서브문자열도 끝났다면 1을 cache에 저장하고 반환한다. ( 와일드카드 서브문자열에 '?'와 일반 문자만이 존재하고 길이도 일치하는 경우이므로 매치되는 경우이다.)

 

두번째 if문

2. 만약 와일드카드 서브문자열이 아직 덜 끝났다면 이건 서브문자열에 '*'이 포함된 경우이다.

이 경우에는 '*'가 몇 글자의 파일이름 문자열과 대응하는지 알 수 없으므로, 와일드카드 서브문자열은 '*' 바로 다음부터 마지막까지 새로운 서브문자열을 만들고, 파일이름 서브 문자열도 한 칸씩 점점 축소시켜가며(왼쪽으로 수렴) 재귀함수를 통해 새로운 매치여부를 확인한다.

 

위 2가지 경우가 아니라면, 모두 매치하지 않는 경우이므로 cache에 0을 넣고 return 0하며 match함수를 종료한다.

 

 

---

 

 

다음은 코드 전체이다.

 

# 입력을 받는 부분
import sys
C = int(sys.stdin.readline())
wildcards = []
filenames = []
for i in range(C):
    # wildcard = sys.stdin.readline()
    # wildcards.append(wildcard[0:-1])
    wildcards.append(sys.stdin.readline())

    N = int(sys.stdin.readline())
    temp = []
    for j in range(N):
        # name = sys.stdin.readline()
        # temp.append(name[0:-1])
        temp.append(sys.stdin.readline())
    filenames.append(temp)


# 문자열의 일치여부를 저장하는 list
# 문자열이 100의 길이 제한을 가지고 있으므로, 
# w와 s의 입력에 대한 출력은 101*101 = 10201개로 제한된다. 

# cache = [[-1]*101]*101

def match_prime(w_prime, s_prime):
    cache = [[-1]*101]*101
    # 입력된 w_prime 과 s_prime의 시작 위치에 따른 접미사만 뽑아서 w, s를 만든다.
    # 각 문자열의 일치 여부를 확인하는 함수.
    def match(w, s): # w는 wildcard pattern, s는 filename.
        if cache[w][s] != -1: # 이것이 memoization.(한 번 들어왔던 입력이면 저장되어 있는 것 바로 출력.)
            return cache[w][s] # 항체같은 것.
        # 인덱스를 하나하나 이동시키며 일치여부를 확인한다. 
        # w의 원소에 ?가 있으면 일치한다고 판단한다.
        # w의 원소에 *이 나오면 거기서부터 끝까지의 새로운 w', s'를 만들어서 재귀로 넘긴다.
        pos = 0
        while (pos < len(w_prime) - w) and (pos < len(s_prime) - s) and (w_prime[w+pos] == '?' or w_prime[w+pos] == s_prime[s+pos]):
            pos += 1

        # 2가지만 확인하고, 나머지는 모두 False를 반환하면 된다.
        # 우선, 패턴의 끝에 도달해서 끝난 경우, 문자열도 함께 끝났는지 확인하고, 문자열도 끝났다면 True.
        # 패턴의 끝에 도달하지 않았는데, while문이 끝났으면 '*'을 만난 경우이다.
        # 패턴의 마지막 char이 '*'이라면 s의 몇 글자가 이 '*'에 대응해야할지 재귀호출을 통해 찾는다.
        # 몇 글자가 대응했는지는 skip이라는 정수형 변수에 입력한다.

        # 1. s가 끝났는데, w도 마침 끝이다. (일치하는 케이스)
        if pos == (len(w_prime) - w) and pos == (len(s_prime) - s):
            cache[w][s] = 1
            return 1 # 1이 True를 의미한다.
        # 2. s가 안끝났다면 이건 '*'을 만난 상황이다. return 이후이므로 elif나 else가 필요 없다.
        if w_prime[w+pos] == '*':
            skip = 0
            while s + pos + skip < len(s_prime):
                if match(w + pos + 1, s + pos + skip) == 1:
                    cache[w][s] = 1
                    return 1
                skip += 1
        # 나머지의 경우는 모두 False를 의미하는 0을 반환시킨다.
        cache[w][s] = 0
        return 0


    temp = match(0, 0) # 최초 입력은 인덱스 (0, 0)

    if temp == 1:
        print(s_prime[0:-1])
        return True
    else:
        return False


print('-----Wildcard와 입력에 대한 일치여부-----')
# w_prime, s_prime을 입력하는 부분. (main과 같은 부분)
for i in range(C):
    ret = 0
    print(wildcards[i][0:-1],'와 일치하는 filename들은 다음과 같다.')
    for name in filenames[i]:
        if match_prime(wildcards[i], name):
            ret += 1   
    print(i+1,'번째 케이스에서 일치의 횟수는 ',ret)
    

 

추가설명:

cache가 101 * 101의 list인 이유: 와일드카드와 파일이름 둘 다 문자열의 길이가 100까지 가능하므로, 문자열의 시작 위치 인덱스가 101개씩 있다. 따라서, 조합해보면 match_prime에 입력된 한쌍의 문자열에 대하여 나올 수 있는 모든 match 여부는 101*101개가 존재한다. 그리고 match함수의 입력도 w, s로 한다. <- 이 w, s가 cache[w][s]에서의 w, s와 같다.

 

 

아쉬운 점:

Python에서 포인터가 없어서 주소참조가 안된다. 그래서 인덱싱이 너무 어렵다ㅠㅠㅠㅠ