와일드카드

풀이

완전 탐색 알고리즘

이 문제는 *을 해결하는 것이 어렵습니다. 알파벳이나 ?는 한글자씩 넘어가며 검사하면 되지만 *에 해당되는 글자는 몇 글자인지 모르기 때문에 모든 경우의 수를 계산해봐야 합니다. 따라서 일단 글자를 하나씩 맞춰보고 *를 만나거나 둘 중 한 문자열이 끝날 때에 멈춥니다. 와일드카드 $wildCard$가 원문 $str$에 대응되는지 여부를 반환하는 함수 $match(wildCard, str)$를 만들어 봅시다. 이 함수의 첫 부분은 다음과 같을 것입니다.

// 와일드카드 패턴 w가 문자열 s에 대응되는지 여부를 반환한다.
public boolean match(final String wildCard, final String str) {
	// wildCard[pos]와 str[pos]를 맞춰나간다.
    int pos = 0;
    while (pos < str.size() && pos < wildCard.size() && (wildCard[pos] == '?' || wildCard[pos] == str[pos]))
    	pos++;
    ..
}

while 문은 $wildCard$와 $str$를 더이상 맞춰 나갈 수 없을 때 종료합니다. 종료하는 경우의 수를 좀더 자세히 따져 봅시다.

1. $str[pos]$와 $wildCard[pos]$가 대응되지 않는다: 당연히 대응 실패입니다.
2. $wildCard$ 끝에 도달했다: 패턴에 *이 하나도 없는 경우 이렇습니다. 이 경우 패턴과 문자열의 길이가 정확히 같아야만 패턴과 문자열이 대응됩니다.
3. $str$ 끝에 도달했다: 패턴은 남았지만 문자열이 남은 경우 만약 문자열이 *만 남았다면 대응 성공이지만 그렇지 않을 경우 대응 실패입니다.
4. $wildCard[pos]$가 *인 경우: *가 몇 글자에 대응될지 모르기 때문에, 0글자부터 남은 문자열의 길이까지를 순회하며 모든 가능성을 검사합니다. 이때 $wildCard$의 $pos + 1$이 후를 패턴 $wildCard'$로 하고, $str$의 $pos + skip$ 이후를 문자열 $str'$로 해서 $match(wildCard', str')$로 재귀 호출했을 때 답이 하나라도 참이면 답은 참이 됩니다.
   아래는 이 아이디어를 구현한 코드입니다.

    // 와일드카드 패턴 wildCard가 문자열 str에 대응되는지 여부를 반환한다.
    public static boolean match(final String wildCard, final String str) {
        // wildCard[pos]와 str[pos]를 맞춰나간다.
        int pos = 0;
        while (pos < str.length() && pos < wildCard.length() && (wildCard.charAt(pos) == '?' || wildCard.charAt(pos) == str.charAt(pos)))
            pos++;
        // 더이상 대응할 수 없으면 왜 while문이 끝났는지 확인한다.
        // 2. 패턴 끝에 도달해서 끝난 경우: 문자열도 끝났어야 대응됨
        if (pos == wildCard.length())
            return pos == str.length();
        // 4. *를 만나서 끝난 경우: *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인한다.
        if (wildCard.charAt(pos) == '*')
            for (int skip = 0; pos + skip <= str.length(); skip++)
                if (match(wildCard.substring(pos + 1), str.substring(pos + skip)))
                    return true;
        // 이 외의 경우에는 모두 대응되지 않는다.
        return false;
    }

여기서 3번을 구현하지 않은 것을 알 수 있는데 그 이유는 4번을 구현하면 자연스럽게 3번도 처리할 수 있기 때문입니다.

중복되는 부분 문제

$match()$ 함수는 참조적 투명 함수이므로 주어질 수 있는 모든 $wildCard$와 $str$에 대응되는 답을 캐시에 저장한다면 중복되는 부분 문제를 더 빨리 풀 수 있을 것입니다. 재귀 호출을 할 때 우리는 항상 $wildCard$와 $str$의 앞에서만 글자들을 떼내기 때문에 $wildCard$와 $str$은 항상 입력에 주어진 패턴 $W$와 파일명 $S$의 접미사가 됩니다. 따라서 입력으로 주어질 수 있는 $wildCard$와 $str$은 각각 최대 101개밖에 없습니다. (문자열의 길이는 각각 최대 100이기 때문입니다.) 이때 $match()$가 $101 \times 101 = 10201$번 이상 호출되었다면 비둘기집의 원리에 따라 어떤 부분 문제가 반드시 여러 번 계산되고 있다는 뜻입니다.
메모이제이션을 사용해 이 상황을 해결하려면 입력값의 모든 경우의 수를 캐시에 저장해야 합니다. $match()$ 함수에 들어갈 입력값 $wildCard$는 전체 패턴 $W$와 $wildCard$의 길이로 특정할 수 있습니다. 따라서 $cache[101][101]$배열에 모든 부분 문제의 답을 저장할 수 있습니다.
아래는 메모이제이션을 이용해 같은 알고리즘을 구현한 것입니다. 더이상 문자열을 재귀 호출의 인자로 넘기지 않고 두 문자열의 시작 위치만을 넘깁니다. 이렇게 하면 함수를 재귀 호출 할 때마다 문자열 객체를 생성하지 않습니다.

구현

import java.util.*;

public class Main {

    // 와일드카드
    public static String wildCard;
    // 검사할 문자열 리스트
    public static String[] strings;
    // 캐시
    public static int cache[][];
    // 답
    public static ArrayList<String> result;

    // 데이터를 입력받는 메소드
    public static void input(Scanner scanner) {
        wildCard = scanner.next();
        int size = scanner.nextInt();
        strings = new String[size];
        for (int i = 0; i < size; i++) {
            strings[i] = scanner.next();
        }

        result = new ArrayList<>();
    }

    // 문제를 해결하는 메소드
    public static void solve() {
        for (int idx = 0; idx < strings.length; idx++) {
            cache = new int[101][101];
            for (int i = 0; i < 101; i++) {
                Arrays.fill(cache[i], -1);
            }
            if (match(0, 0, idx) == 1)
                result.add(strings[idx]);
        }
    }

    // 와일드카드 패턴 wildCard가 문자열 str에 대응되는지 여부를 반환한다.
    public static int match(int w, int s, int idx) {
        // 메모이제이션
        if (cache[w][s] != -1) return cache[w][s];
        // wildCard[pos]와 str[pos]를 맞춰나간다.
        while (s < strings[idx].length() && w < wildCard.length() && (wildCard.charAt(w) == '?' || wildCard.charAt(w) == strings[idx].charAt(s))) {
            w++;
            s++;
        }
        // 더이상 대응할 수 없으면 왜 while문이 끝났는지 확인한다.
        // 2. 패턴 끝에 도달해서 끝난 경우: 문자열도 끝났어야 대응됨
        if (w == wildCard.length()) {
            return cache[w][s] = (s == strings[idx].length() ? 1 : 0);
        }
        // 4. *를 만나서 끝난 경우: *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인한다.
        if (wildCard.charAt(w) == '*')
            for (int skip = 0; s + skip <= strings[idx].length(); skip++)
                if (match(w + 1, s + skip, idx) == 1)
                    return cache[w][s] = 1;
        // 이 외의 경우에는 모두 대응되지 않는다.
        return cache[w][s] = 0;
    }

    // 답을 출력하는 메소드
    public static void output() {
        Collections.sort(result);
        for (String str : result) {
            System.out.println(str);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

시간 복잡도 분석

패턴과 문자열의 길이가 모두 $n$이라고 할 때, 부분 문제의 개수는 $n^2$입니다. $match()$ 함수는 한 번 호출될 때마다 최대 $n$번의 재귀 호출을 하기 때문에 전체 시간 복잡도는 $O(n^3)$입니다.

다른 분해 방법

사실 $O(n^2)$ 시간에 풀 수 있는 방법이 있습니다. 위의 코드가 $O(n^3)$ 시간이 걸리는 것은 내부에서 첫 *를 찾고, *에 몇 글자가 대응되어야 할지 검사하는 반복문이 존재하기 때문입니다. 만약 재귀 함수 자체에 반복문이 하나도 없도록 코드를 바꿀 수 있다면 우리는 부분 문제 개수와 같은 시간만을 사용해 문제를 풀 수 있을 것입니다.
wildCard.charAt(w)와 strings[idx].charAt(s)가 서로 대응되는지 검사하는 while문의 조건을 통과하면 원래는 w++; s++;를 실행했지만 이렇게 하지 말고 패턴과 문자열의 첫 한 글자씩을 떼고 이들이 서로 대응되는지를 재귀 호출로 확인할 수 있습니다.

while (w < wildCard.length() && s < strings[idx].length() && (wildCard.charAt(w) == '?' || wildCard.charAt(w) == strings[idx].charAt(s))) {
    return cache[w][s] = match(w + 1, s + 1, idx);
}

다음으로 *에 몇 글자가 대응되어야 할 지를 확인하는 반복문을 재귀 호출로 바꿔 봅시다. 1차원 for문을 재귀 호출로 바꾸는 것은 간단합니다. 매 단계에서 *에 아무 글자도 대응시키지 않을 것인지, 아니면 한 글자를 더 대응시킬 것인가를 결정하면 됩니다.

회고

참고문헌: 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 인사이트, (2012)