WILDCARD 문제 책의 정답을 넣어봤는데 오답이 뜹니다.

  • kwangswei
    kwangswei

    으, 멘붕 상태군요.
    제가 구현한 방식대로 하면 자꾸 오답이 떠서,
    결국 책에 답을 보고 구현해보았습니다.
    그리고 제출했는데 "오답" -_-;;;

    오타가 난건 아닌지 몇 번 봤는데 오타는 아닌 것 같습니다.
    ( 멘붕 상태라 발견을 못한 것일수도 -_-;;; )

    확인 부탁 드립니다.
    감사합니다.

    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;
    }
    

    6년 전
8개의 댓글이 있습니다.
  • VOCList
    VOCList

    제가 과거에 맞았던 소스를 열어봤는데, 왠지는 모르겠지만 매 테스트 케이스에 대해서 답이 될 수 있는 단어 목록들을 정렬해서 사전순서대로 출력했네요. 위 소스도 cout 부분을 바로 찍지 않고 모아서 정렬 한 뒤 출력하도록 수정했더니 AC가 뜹니다.
    아마 예전 문제에는 사전순이란 말이 있었는데 어느새 사라진 게 아닌가 추측이 되네요. 데이터나 문제가 수정되어야 할 것 같습니다.


    6년 전 link
  • VOCList
    VOCList

    틀린 문제가 하나씩 나올 때마다 저지를 의심하는 사람은 늘어만 갈 텐데 말이지요 ㅠㅠ


    6년 전 link
  • ggabu420
    ggabu420

    문제 출력 부분에 알파벳 순으로 출력하라고 되어있지 않나요? 그래서 저도 그렇게 출력했습니다만..


    6년 전 link
  • kwangswei
    kwangswei

    으아아아아아악!!!
    죄송합니다 ㅠ.ㅠ
    문제도 제대로 안 읽다니......
    멘붕 상태에서는 문제부터 차분히 다시 검토해야겠습니다.
    감사합니다!!


    6년 전 link
  • kwangswei
    kwangswei

    제가 생각했던 방법도 "정답" 판정 받았습니다.

    저지 서버의 문제가 아니라 제가 문제를 잘못 읽은 것 입니다.
    안심하셔요 ^^;;;

    답변 감사합니다.


    6년 전 link
  • VOCList
    VOCList

    헉 알파벳순이라고 써져있넹 새벽엔 왜 못봤지
    ...
    ㅠㅠ


    6년 전 link
  • ppstpsj
    ppstpsj

    저도 그거 안읽고 했다가 ㅠㅠㅠㅠㅠㅠ


    6년 전 link
  • JongMan
    JongMan

    휴 제가 어제 애보다가

    틀린 문제가 하나씩 나올 때마다 저지를 의심하는 사람은 늘어만 갈 텐데 말이지요 ㅠㅠ

    여기까지 보고 아 또 실수했구나 이런 ㅠㅠㅠ 하고 울며 잠들었는데 다행이군요. ㅋㅋㅋㅋ


    6년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.