WILDCARD

■ 문제

'?'와'*'가 포함된 와일드카드 문자열 w(숫자+대/소문자와+'?'+'*') 문자열 s(숫자+대/소문자)와의 매칭 여부를 확인하는 문제다.

■ 풀이

문제를 해결에 2가지를 구현하는 것이 핵심이다

1. brute-force한 완전탐색 로직 구현

2. 중복 탐색(비둘기집 원리)이 발생함을 이해하고 메모이제이션을 적용

1. brute-force한 완전탐색 로직 구현

w와 s에 대한 인덱스 wIdx, sIdx를 활용하여 문자(char) 비교를 시행하고 아래 4가지 조건에 맞게 분기하여 재귀적으로 처리한다.

① w[wIdx]와 s[sIdx]가 대응되지 않는 경우

w[wIdx]가 ? 또는 *가 아니며 s[sIdx]와 매칭이 안되는 경우로, 대응 실패이다.

② w 끝에 도달

패턴 w에 대한 wIdx가 끝에 도달한 경우로, sIdx도 s 끝에 도달해야만 두 문자열이 대응된다고 할 수 있다.

③ s 끝에 도달

패턴 w가 끝에 도달하지 못했지만, s는 끝에 도달한 경우로 남은 w가 모두 *가 아니라면, 대응이 실패

④ w[wIdx]가 *인 경우

*가 s의 몇 글자에 대응되는지 알 수 없기 때문에 0글자부터 남은 문자열의 길이까지 순회하며 모든 가능성을 검사해야한다.

match(wIdx+1, sIdx+next), sIdx+next가 문자열 s 길이보다 작거나 같아야 하는 조건으로 순회해야 한다.

2. 중복 탐색(비둘기집 원리)이 발생함을 이해하고 메모이제이션을 적용

w와 s는 각각 최대 길이 100의 문자열이다. w가 모두 *라고 생각한다면 부분문제는 101*101개다.

하지만 부분문제에 대한 매칭 여부를 확인하는데 재귀호출을 진행함에 있어서 중복 탐색이 발생한다.

   

첫번째, 두번째 *가 문자열 0개 매칭하고, 세번째 *가 abc를 매칭하는 경우이며,

첫번째, 세번째 *가 문자열 0개 매칭하고, 두번째 *가 abc를 매칭하는 경우에 대한 예시이다.

위 빨간색 박싱된 부분은 기존에 확인했던 부분으로 재접근하여 확인하는 로직이다. 따라서, 해당 메모이제이션을 통해 매칭 가능 여부 결과를 기록해놓면 된다.

결과적으로 부분문제 갯수인 n*n으로  O(n^2)이 되며,

부분문제 시작점에서 재귀호출이 발생하는 횟수는 최대 n으로 시간복잡도는 O(n^3)이 된다.

재귀 함수 자체에 반복문이 하나도 없도록 코드를 수정하면 부문 문제 개수와 같은 시간만 이용해 문제 결이 가능하며, 결과적으로 O(n^2)이 된다.