[알고스팟] WILDCARD - Wildcard/와일드 카드 (C++)

문제

https://algospot.com/judge/problem/read/WILDCARD

algospot.com :: WILDCARD

 

풀이

다이나믹 프로그래밍 문제이지만, 단순히 메모이제이션을 적용할 수 없어서 어려웠다. 풀이는 알고리즘 문제 해결 전략(일명 종만북)을 참조하였다.

 

와일드 카드(wild_card)와 파일명(file_name)을 한 글자씩 비교하여 진행할 경우

글자가 같은 경우와 와일드 카드의 ? 문자는  다음 칸으로 넘어가는 것으로 간단히 구현이 가능하다. 

 

하지만 와일드 카드의 *의 경우 0글자 이상인 모든 문자열과 일치하기 때문에 *가 등장한 위치의 다음 칸(wild_idx+1)에서 부터  file_name의 현재 위치(file_idx)에서 문자열의 끝까지 모두 재귀 호출로 탐색을 해보아야 한다. 즉, *가 어느 문자까지를 일치시켜 넘기는지 구현한다.

 

처음에는 해당 문제를 구현하는데 메모이제이션 기법이 필요한 부분을 찾지 못하였는데 아래와 같은 경우를 생각해보자.

 

int matchWildCard(int wild_idx, int file_idx)

이는 재귀호출을 통해 wild_idx와 file_idx가 동시에 종료되는 경우에만 true(1)을 반환하는 재귀 함수이다.

 

입력

wild_card: *****u***

file_name: apppppapupp

(해당 입력과 같이 모든 경우를 탐색하여도 결국 결국 답이 나오지 않을 경우 시간 초과를 유발한다. DP문제에서는 이와 같은 경우를 생각해보고 메모이제이션 적용방안을 생각해보자.)

 

가장 먼저 matchWildCard(0, 0) 이 호출되면,

wild_card의 첫 번째 *(위치, wild_idx: 0)가 등장하면 해당 *를 넘긴 wild_idx+1 위치에서 file_idx(0~끝까지)를 재귀 호출하여 탐색한다.

 

재귀 호출을 통해 가장 먼저 호출되는 matchWildCard(1, 0)에서도 이러한 과정은 두 번째 *(위치, wild_idx: 1)에서 똑같이 반복된다. 따라서 matchWildCard(2, 0) -> matchWildCard(2, 1) ->...  -> matchWildCard(2, 10) 순으로 호출이 이루어진다. 

 

만약 matchWildCard(1, 0)의 호출이 모두 종료되어 값이 반환되었다면 다음으로 file_idx를 1 증가시킨 matchWildCard(1, 1)를 호출시킨다. 하지만 해당 함수에서 호출하는 matchWildCard(2, 1)-> matchWildCard(2, 2) ->...  -> matchWildCard(2, 10) 의 재귀 호출은

이미 matchWildCard(1, 0)에서 호출된 값들이다. 즉, 중복된 호출이 발생하여 계산의 효율이 떨어진다.

 

이를 메모이제이션으로 값을 저장한다면 모든 호출은 단 한 번의 연산만으로 해결이 가능하다.

따라서 cache[wild_idx][file_idx]에 해당 위치들에서 탐색 시 매칭이 가능한지의 여부를 저장하여 구현한다.

 

 

마지막으로 매칭된 값들은 아스키코드값으로 정렬 후 출력하는 것을 잊지 말자.

 

코드