와일드카드 패턴 매칭 알고리즘

이 문제에서는 하나의 메인 문자열과 와일드카드 패턴이 주어지며, 주어진 와일드카드 패턴이 메인 텍스트와 일치하는지 여부를 판별하는 것이 목표입니다.

와일드카드 패턴은 일반 문자 외에도 '*' 또는 '?' 기호를 포함할 수 있습니다. '?'는 임의의 단일 문자 하나와 대응되고, '*'는 빈 문자열을 포함한 임의 길이의 문자 시퀀스와 대응됩니다.

매칭 규칙

'*'를 만난 경우: 별표 문자 자체를 건너뛰고 패턴의 다음 문자 검사로 진행할 수 있습니다.
'?'를 만난 경우: 텍스트의 현재 문자 하나만 소비하고, 패턴과 텍스트 모두 다음 문자로 넘어갑니다.
일반 문자인 경우: 패턴과 텍스트의 현재 문자가 서로 일치할 때만 다음 단계로 진행할 수 있습니다.

입력 및 출력 예시

입력:
메인 문자열과 와일드카드 패턴
메인 문자열: "Algorithm"
패턴: "A*it?m"

출력:
패턴이 일치합니다.

알고리즘

wildcardMatch(text, pattern)

입력: 메인 텍스트와 와일드카드 패턴

출력: 패턴이 메인 텍스트와 일치하면 true, 아니면 false

시작
    n := 텍스트의 길이
    m := 패턴의 길이

    만약 m = 0이라면
        n = 0이면 0을 반환, 그렇지 않으면 1을 반환
    i := 0, j := 0

    i < n 인 동안 반복:
        text[i] == pattern[j] 라면
            i를 1 증가
            j를 1 증가
        아니고 j < m 이며 pattern[j]가 '?'라면
            i를 1 증가
            j를 1 증가
        아니고 j < m 이며 pattern[j]가 '*'라면
            textPointer := i
            patPointer := j
            j를 1 증가
        아니고 patPointer가 갱신된 적이 있다면
            j := patPointer + 1
            i := textPointer + 1
            textPointer를 1 증가
        아니면
            false 반환
    반복 끝

    j < m 이고 pattern[j]가 '*'인 동안
        j를 1 증가
    반복 끝

    만약 j = m 이라면
        true 반환
    false 반환
끝

동작 원리

이 알고리즘은 두 개의 포인터(i, j)를 사용해 텍스트와 패턴을 순차적으로 비교합니다. 핵심은 '*'를 만나는 순간 그 위치를 저장해 두고(textPointer, pattPointer), 이후 비교에 실패하면 마지막 '*' 위치로 되돌아가 별표가 소비하는 문자 수를 하나씩 늘려가며 다시 시도하는 백트래킹(backtracking) 방식이라는 점입니다. 이를 통해 '*'가 실제로 몇 글자에 대응해야 하는지 미리 알지 못해도 올바른 매칭 결과를 얻을 수 있습니다.

시간 복잡도는 최악의 경우 O(n×m)이며, 추가 배열 없이 상수 크기의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 동적 계획법(DP)으로도 풀 수 있지만, 이 방식은 메모리를 절약할 수 있다는 장점이 있습니다.

C++ 구현 예제

#include<iostream>
using namespace std;

bool wildcardMatch(string text, string pattern) {
    int n = text.size();
    int m = pattern.size();

    if (m == 0)      // 패턴이 빈 문자열인 경우
        return (n == 0);

    int i = 0, j = 0, textPointer = -1, pattPointer = -1;
    while (i < n) {
        if (text[i] == pattern[j]) {      // 텍스트와 패턴의 문자가 일치
            i++;
            j++;
        } else if (j < m && pattern[j] == '?') {      // ?는 임의의 한 문자에 대응
            i++;
            j++;
        } else if (j < m && pattern[j] == '*') {      // *는 임의의 문자열에 대응
            textPointer = i;
            pattPointer = j;
            j++;
        } else if (pattPointer != -1) {      // 마지막 '*' 위치로 백트래킹
            j = pattPointer + 1;
            i = textPointer + 1;
            textPointer++;
        } else
            return false;
    }

    while (j < m && pattern[j] == '*') {
        j++;      // 텍스트가 끝난 후 남은 '*' 처리
    }

    if (j == m) {      // 패턴을 끝까지 처리했는지 확인
        return true;
    }

    return false;
}

int main() {
    string text;
    string pattern;
    cout << "텍스트 입력: "; cin >> text;
    cout << "와일드카드 패턴 입력: "; cin >> pattern;

    if (wildcardMatch(text, pattern))
        cout << "패턴이 일치합니다." << endl;
    else
        cout << "패턴이 일치하지 않습니다" << endl;
}

실행 결과

텍스트 입력: Algorithm
와일드카드 패턴 입력: A*it?m
패턴이 일치합니다.