NAMING문제를 풀면서 질문 드립니다..

  • cheh344
    cheh344

    http://www.algospot.com/judge/problem/read/NAMING

    잘 안풀려서 질문답변 게시판을 찾아보고 하니 오답이 나올 경우가

    1. 배열을 너무 크게 잡아서 할당된 메모리 크기를 넘어간다
    2. 복잡도가 O(n^2)를 넘어가면 워스트케이스에서 시간초과가 일어난다
    3. 배열을 다시 사용하면서 다시 초기화를 하지 않아 쓰레가 값이 남아있다.

    딱 떠오르는건 이 세가지 정도 있는데요

    풀어보면서 시간복잡도 문제는 확인이 되었는데 다만 다른 두 케이스는 어떻게 잡아야 할지 모르겠네요

    배열크기문제는 컴파일에러 같은거로 뜰 것 같은데 소스코드 제출하면 그냥 오답이라고 하고... 배열에 쓰래기 값이 남아있나 해서 각 테스트 케이스가 끝날때마다 그냥 할당된 크기를 싸그리 다 널값으로 초기화 해 주었는데 여전히 오답이군요ㅎㅎ

    알고리즘을 잘못짰나 싶기엔 여러 문장을 만들어서 넣어보니 나오긴 잘 나오고...

    조언 부탁드립니다ㅎㅎ

    아래는 제가 작성한 소스코드입니다

    void Naming() {
        cin>>fullName>>addName;
        strcat(fullName, addName);
        //cout<<fullName<<endl;
        int fLen = strlen(fullName);
    
        for(int i = 0; i < fLen; i++) {
            pre[i] = fullName[i];// make prefix to compare
            //cout<<pre<<" ";
    
            for (int j = 0; j <= MAXI; j++)
                tmp[j] = '\0'; //return temp string
    
            tmp[0]= fullName[fLen-(i+1)];
            strcat(tmp, post); // make postfix to compare
    
            //cout<<tmp<<" ";
            if (strcmp(pre, tmp)==0) // Is each string same ?
                cout<<i+1<<" ";
            strcpy(post, tmp);
        } // for loop end.
        cout<<endl;
        for (int i = 0;i < MAXI;i++) {
            fullName[i]='\0';
            addName[i]='\0';
            pre[i]='\0';
            post[i]='\0';
            tmp[i]='\0';
        }
    }
    

    11년 전
2개의 댓글이 있습니다.
  • yeonzzg
    yeonzzg

    제 기억으로 이 문제는 특수한 알고리즘을 알아야 푸는걸로 기억되네요..

    KMP algorithm이라고 구글에 검색해보세요


    11년 전 link
  • cheh344
    cheh344

    좋은 조언 감사합니다!


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