SORTGAME를 알고리즘 문제해결 전략 책의 코드로 했는데 시간초과 떠요..

  • swqasw
    swqasw

    알고리즘 문제해결 전략의 코드 29.4를 이용해서 문제를 풀었습니다.

    책에서는 n=8인 경우에도 40320개의 상태만 방문하면 되므로 precalc() 수행시간이 오래걸리지 않는다고 적혀있습니다.

    그런데 코드 작성 후 돌려보니 n=8일때 맵 만드는데 한참 걸립니다.

    이유가 무엇인지 알려주시면 감사하겠습니다.

    아래 코드는 책보고 따라한 코드

    #include <iostream>
    #include <vector> 
    #include <algorithm>
    #include <queue> 
    #include <map> 
    using namespace std;
    map<vector<int>, int> toSort;
    void precalc(int n) {
        vector<int> perm(n);
        for (int i = 0;i < n;i++) perm[i] = i;
        queue<vector<int> > q;
        q.push(perm);
        toSort[perm] = 0;
        while (!q.empty()) {
            vector<int> here = q.front();
            q.pop();
            int cost = toSort[here];
            for (int i = 0;i < n;i++) {
                for (int j = i + 2;j <= n;j++) {
                    reverse(here.begin() + i, here.begin() + j);
                    if (toSort.count(here) == 0) {
                        toSort[here] = cost + 1;
                        q.push(here);
                    }
                    reverse(here.begin() + i, here.begin() + j);
                }
            }
        }
    }
    int solve(const vector<int>& perm) {
        int n = perm.size();
        //sort(perm, perm + n);
        vector<int> fixed(n);
        for (int i = 0;i < n;i++) {
            int smaller = 0;
            for (int j = 0;j < n;j++) {
                if (perm[j] < perm[i]) ++smaller;
            }
            fixed[i] = smaller;
        }
        return toSort[fixed];
    }
    int main() {
        int testCase;
        cin >> testCase;
        vector<int> result(testCase);
        for (int i = 0;i < testCase;i++) {
            int n;
            cin >> n;
            vector<int> perm(n);
            for (int j = 0;j < n;j++) cin >> perm[j];
            toSort.clear();
            precalc(n);
            result[i] = solve(perm);
        }
        for (int i = 0;i < testCase;i++) {
            cout << result[i] << endl;
        }
        return 0;
    }
    

    1년 전
1개의 댓글이 있습니다.
  • sgchoi5
    sgchoi5
    for (int i = 1; i <= 8; i++)
        precalc(i);

    를 testCase for 문 전에 미리 해주시면 됩니다. 전처리 후 각 testcase 에서 사용하는 것입니다.


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