으, 멘붕 상태군요.
제가 구현한 방식대로 하면 자꾸 오답이 떠서,
결국 책에 답을 보고 구현해보았습니다.
그리고 제출했는데 "오답" -_-;;;
오타가 난건 아닌지 몇 번 봤는데 오타는 아닌 것 같습니다.
( 멘붕 상태라 발견을 못한 것일수도 -_-;;; )
확인 부탁 드립니다.
감사합니다.
[[problem:WILDCARD]]
책 223~225p
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int cache[101][101];
string W,S;
int IsMatched(int w, int s)
{
int& ret = cache[w][s];
if ( ret != -1)
return ret;
if ( w < W.size() && s < S.size() && (W[w] == '?' || W[w] == S[s] ))
return ret = IsMatched(w+1, s+1);
if ( w == W.size())
return ret = (s == S.size() );
if ( W[w] == '*' )
if ( IsMatched(w+1, s) || ( s < S.size() && IsMatched(w, s+1)))
return ret = 1;
return ret = 0;
}
int main()
{
int T;
cin >> T;
while ( T-- )
{
cin >> W;
int inputCnt;
cin >> inputCnt;
for ( int i = 0; i < inputCnt; i++ )
{
memset( cache, -1, sizeof(cache));
cin >> S;
if ( IsMatched(0, 0) )
cout << S << endl;
}
}
return 0;
}
제가 과거에 맞았던 소스를 열어봤는데, 왠지는 모르겠지만 매 테스트 케이스에 대해서 답이 될 수 있는 단어 목록들을 정렬해서 사전순서대로 출력했네요. 위 소스도 cout 부분을 바로 찍지 않고 모아서 정렬 한 뒤 출력하도록 수정했더니 AC가 뜹니다.
아마 예전 문제에는 사전순이란 말이 있었는데 어느새 사라진 게 아닌가 추측이 되네요. 데이터나 문제가 수정되어야 할 것 같습니다.
kwangswei
으, 멘붕 상태군요.
제가 구현한 방식대로 하면 자꾸 오답이 떠서,
결국 책에 답을 보고 구현해보았습니다.
그리고 제출했는데 "오답" -_-;;;
오타가 난건 아닌지 몇 번 봤는데 오타는 아닌 것 같습니다.
( 멘붕 상태라 발견을 못한 것일수도 -_-;;; )
확인 부탁 드립니다.
감사합니다.
[[problem:WILDCARD]]
책 223~225p
13년 전