JAEHASAFE 시간 초과 이유가 뭘까요?

  • robustFlame
    robustFlame

    문제 링크
    책에서는

    • 테스트 케이스의 수 : C(1 <= C <= 50)
    • 상태의 수 : N(1 <= N <= 100)
    • 문자열의 최대 길이 L : 10000 (해당 문제 링크에서는 테스트 케이스의 수는 주어지지 않고 상태의 수 N이 최대 50입니다.)

    아래 코드에서 문제를 해결하는 알고리즘은 책에 나와있는 알고리즘과 거의 비슷합니다. 문자열 검색을 이용하여 각 상태에서 다음 상태로 최소 다이얼 이동을 하여야 하는지 알아내어 최종 다이얼 이동 수를 알아냅니다. 문자열 비교시에 KMP 알고리즘(책 코드 사용)을 사용하기에 시간복잡도는 O(L)압나다. 상태의 수(최대100)와 테스트 케이스(최대50)의 수를 감안하더라도 시간내에 성공할 줄 알았는데 시간초과가 됩니다. 무엇이 문제일까요??

    #include <iostream>
    #include <vector>
    #include <string>
    #include <algorithm>
    using namespace std;
    
    // 부분 일치 테이블 생성 (KMP 문자열 검색 알고리즘 전처리 과정)
    vector<int> getPartialMatch(const string& N) {
        int m = N.size();
        vector<int> pi(m, 0);
        int begin = 1, matched = 0;
        while (begin + matched < m) {
            if (N[begin + matched] == N[matched]) {
                matched++;
                pi[begin + matched - 1] = matched;
            }
            else {
                if (matched == 0)
                    begin++;
                else {
                    begin += matched - pi[matched - 1];
                    matched = pi[matched - 1];
                }
            }
        }
        return pi;
    }
    // '짚더미' H의 부분 문자열로 '바늘' N이 출현하는 첫 시작 위치를 반환한다.
    int kmpSearch(const string& H, const string& N) {
        int n = H.size(), m = N.size();
        int result = 0;
        vector<int> pi = getPartialMatch(N);
        int begin = 0, matched = 0;
        while (begin <= n - m) {
            if (matched < m && H[begin + matched] == N[matched]) {
                matched++;
                if (matched == m) {
                    result = begin;
                    // 최소 다이얼 이동만 알면 되므로 break
                    break;
                }
            }
            else {
                if (matched == 0) 
                    begin++;
                else {
                    begin += matched - pi[matched - 1];
                    matched = pi[matched - 1];
                }
            }
        }
        return result;
    }
    // 
    int minMoveOfDial(const int numOfStates) {
        int result = 0;
        string A, B;
        cin >> A;   // 처음 상태입력
        // 인접한 각 상태들 간의 최소 다이얼 이동을 구하여 결과에 더한다.
        for (int i = 0; i < numOfStates; i++) {
            if (i % 2 == 0) {   // 반시계 방향으로 회전해야 하는 경우
                cin >> B;
                result += kmpSearch(A + A, B);
            }
            else {              // 시계 방향으로 회전해야 하는 경우
                cin >> A;
                result += kmpSearch(B + B, A);
            }
        }
        return result;
    }
    
    int main() {
        std::ios::sync_with_stdio(false);   // cin의 성능 향상을 위함
        int numOfCases;
        cin >> numOfCases;
        while (numOfCases) {
            int numOfStates;
            cin >> numOfStates;
            cout << minMoveOfDial(numOfStates) << endl;
    
        }
    }
    

    3년 전
2개의 댓글이 있습니다.
  • Signin
    Signin

    살펴봤는데 numOfCases가 안 줄어드네요 :)


    3년 전 link
  • robustFlame
    robustFlame

    ㄴ그렇네요;; 감사합니다.


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