- 1. Problem
- 2. My Approach
- 3. Implementation
- 4. Textbook Approach
- 5. Implementation
- 6. Analysis
- 7. Feedback
1. Problem
2. My Approach
- 함수
judgewild(wild_idx, card_idx)는 와일드카드(wildcard)와 파일명(card)를 입력받으면 인덱스 0부터 비교를 시작한다. - wildcard[w]가 단순 문자일 경우 card[c]와 비교하여 맞으면 다음 인덱스로 넘어가 judgewild를 재귀호출한다.
- wildcard[w]가 ‘?’인 경우 card[c]와 맞다고 하고 다음 인덱스로 넘어간다.
- wildcard[w]가 ‘*‘인 경우 변수 skip과 함께 무한 루프로 진입한다.
- 변수 skip은 해당 ‘*‘에 card의 몇개의 문자가 대응되는 지를 의미한다.
- ‘*‘에는 0개의 문자부터 대응될 수 있으므로 skip은 0부터 시작한다.
- skip은 0부터(대응하는 문자 없음) card.size()까지(나머지 문자 모두 대응)까지 증가하며 각각의 경우에 대응되었다고 가정하고 judgewild가 재귀호출된다.
- while문 안에서 한 가지 skip의 judgewild라도 기저사례까지 도달하여 true를 반환하면 해당 skip만큼 ‘*‘에 대응한 경우가 성립하는 것이므로 최종적으로 true를 반환한다.
3. Implementation
bool judgeWild(int wild_idx, int card_idx){
//base case
if(wild_idx==wildcard.size() && card_idx == card.size())
return true;
// Just a word or '?'
else if(wildcard[wild_idx] == card[card_idx] || (card_idx<card.size() && wildcard[wild_idx] == '?'))
return judgeWild(wild_idx+1, card_idx+1);
// Case of '*'
else if(wildcard[wild_idx] == '*'){
int i=0;
while(true) {
// Test all the case
if(judgeWild(wild_idx+1, card_idx+i)) return true;
if(card_idx+i == card.size()) break;
i++;
}
}
return false;
}
int main( ) {
int T;
cin >> T;
while(T--){
list<string> ret;
int num;
cin >> wildcard;
cin >> num;
while(num--){
cin >> card;
if(judgeWild(0, 0))
ret.push_back(card);
}
ret.sort();
list<string>::iterator it = ret.begin();
while(it != ret.end())
cout<<*(it++)<<endl;
}
return 0;
}
- wildcard에 대응되는 card들을 어순에 맞게 정렬하여 출력해야 하는데, 해당 card를 string타입의 list에 넣고 list.sort() 하여 간단하게 구현하였다.
4. Textbook Approach
- 책 역시 ‘*’ 에 대응하는 문자의 수를 0개부터 card의 남은 문자열수만큼 하나씩 늘려주면서 체크를 해준다.
- 다만 하나의 조건문 안에 재귀함수를 호출하면서 좀 더 재귀적인 구조의 알고리즘을 구현하였다.
- memoization을 적용하여 중복되는 경우를 줄여주었다.
5. Implementation
string w, s;
int cache[101][101];
bool check(int w_idx, int s_idx) {
int& ret = cache[w_idx][s_idx];
if(ret != -1) return ret;
while(w_idx < w.length() && s_idx < s.length() && (w[w_idx] == '?' || w[w_idx] == s[s_idx]))
return ret = check(w_idx + 1, s_idx + 1);
if(w_idx == w.length())
return ret = (s_idx == s.length());
if(w[w_idx] == '*')
if(check(w_idx + 1, s_idx) || (s_idx < s.length() && check(w_idx, s_idx + 1)))
return ret = 1;
return ret = 0;
}
6. Analysis
- 채점서버로 돌려본 결과 본인의 코드는 8ms, 책의 코드는 4ms의 수행시간이 걸렸다.
- 본인의 코드는 while문 안에서 최악의 경우 N번의 재귀호출이 발생하고, 책의 코드 역시 N번의 재귀호출이 일어나 이 부분에 있어선 큰 차이가 없을 것으로 보인다. * 다만 책의 코드에선
memoization을 사용함으로써 중복되는 경우를 줄여주었으니 아마 이 점에서 수행시간이 줄었다고 볼 수 있다.
7. Feedback
- 본 문제는 분할 정복 구조를 사용하여 복잡해 보이는 문제를 쉽게 해결가능한 하부 문제들로 쪼개어 해결한다.
- 문제가 주어지면 가장 먼저 분할정복의 관점에서 바라봐야 할 필요성을 느낀다.
- Memoization은 채점 기준에 따라 적용을 안해도 되지만, 보통 철저한 대회의 경우 Memoization을 이용하여 중복처리를 해주지 않으면 시간초과를 발생하게 한다. 특별한 상황을 제외하고 Memoization을 처리해주는 습관을 기르자.