글 읽기 - 약 63%에서 실패.. 반례가 뭐가있을까요

kimsy96 6년 전 0

우선 *를 포함하는 문자열을 string chk에다 받고,

n번 string s를 입력받으며 비교하였습니다.

우선 chk배열의 '*'의 인덱스를 구한다음, 비교할 문자열 s의 처음부터 idx까지 같은지 구한다음, 같다면 count를 하나씩 올려줬습니다.

그리고 나서 chk배열의 '*' 이후도 비교해줘서, count의 개수가 chk배열의 크기-1과 같다면 DA를 출력하게끔 구현했습니다.

처음에 문제를 풀 때 a*d= a(뭐가오든지상관없고)d 의 경우만 생각하고 풀었는데, 틀리고 문제를 다시 보니 a*d=ad 의 경우도 구해야 되더군요. 그런데 제 풀이를 보니 의도한 건 아니지만 그 경우도 포함하고 있던데 틀렸다고 나오네요.

혹시 반례가 있을까요

#include <string>
#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    string chk;
    cin>>chk;

    int idx;
    for(int q=0;q<chk.size();q++)
        if(chk[q]=='*')
            idx=q;
    while(n--)
    {
        int m=idx;
        int count=0;
        string s;
        cin>>s;
        for(int i=0;i<idx;i++)
        {
            if(s[i]==chk[i])
                count++;

        }
        int k=chk.size()-(idx+1);

        for(int i=s.size()-k;i<s.size();i++)
        {
            if(s[i]==chk[m+1])
                count++;

            m++;
        }



       if(count==chk.size()-1)
            cout<<"DA"<<'\n';
       else
            cout<<"NE"<<'\n';



    }
    return 0;




}

kimsy96 6년 전 0

추가적으로 질문을 하나 더 하고 싶은데

for문안에 strlen(str)을 집어넣으면 시간복잡도가 확 올라서 따로 변수로 strlen(arr)을 받은다음 for 문안에 집어넣는 걸로 알고 있습니다.

제가 공부를 조금씩 하면서 책이라던가 다른 분들 풀이를 종종 보며 공부를 하는데 size함수는 굳이 저렇게 빼서 구하지 않고 반복문안에 넣더군요(그래서 저도 그냥 넣어서 풀고 있습니다.) 둘다 size를 구하는 함수인데 내부 구현이 어떻게 다르길래 이런 결과가 나오는거죠