HABIT 시간초과

  • yongwhan
    yongwhan

    알고리즘 문제해결전략에 있는 풀이를 보고 코드를 작성하였는데 시간초과가 떠서 질문드립니다. 혹시 제가 잘못 작성한 부분이 있는지요? 참고로 책에서는 vector group을 const vector &group으로 작성했는데 그렇게 하면 다음과 같은 에러가 떠서 그렇게 못했습니다.

    error: passing ‘const std::vector’ as ‘this’ argument of ‘std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = int; _Alloc = std::allocator]’ discards qualifiers [-fpermissive]
    group=_group;

    또 cin/cout을 scanf/printf로 바꾸었는데도 시간초과가 뜨네요..

    해결책을 알려주세요. 감사합니다!

    #include<bits/stdc++.h>
    using namespace std;
    
    struct Comparator {
      vector<int> group;
      int t;
      Comparator(const vector<int> &_group, int _t) {
        group=_group;
        t=_t;
      }
      bool operator () (int a, int b) {
        if(group[a]!=group[b]) return group[a]<group[b];
        return group[a+t]<group[b+t];
      }
    };
    
    vector<int> getSuffixArray(const string &s) {
      int n=s.size();
      int t=1;
      vector<int> group(n+1);
      for (int i=0; i<n; i++) group[i]=s[i];
      group[n]=-1;
      vector<int> perm(n);
      for (int i=0; i<n; i++) perm[i]=i;
      while(t<n) {
        Comparator compareUsing2T(group, t);
        sort(perm.begin(), perm.end(), compareUsing2T);
        t*=2;
        if(t>=n) break;
        vector<int> newGroup(n+1);
        newGroup[n]=-1;
        newGroup[perm[0]]=0;
        for (int i=1; i<n; i++)
          if(compareUsing2T(perm[i-1], perm[i]))
            newGroup[perm[i]]=newGroup[perm[i-1]]+1;
          else
            newGroup[perm[i]]=newGroup[perm[i-1]];
        group=newGroup;
      }
      return perm;
    }
    
    int commonPrefix(const string &s, int i, int j) {
      int k=0;
      while(i<s.size() && j<s.size() && s[i]==s[j]) {
        i++; j++; k++;
      }
      return k;
    }
    
    int longestFrequent(int k, const string &s) {
      vector<int> a=getSuffixArray(s);
      int ret=0;
      for (int i=0; i+k<=s.size(); i++)
        ret=max(ret, commonPrefix(s, a[i], a[i+k-1]));
      return ret;
    }
    
    int main() {
      ios_base::sync_with_stdio(false);
      cin.tie(0);
      cout.tie(0);
    
      int t; cin>>t;
      while(t--) {
        int k; string s; cin>>k>>s;
        cout << longestFrequent(k,s) << endl;
      }
      return 0;
    }
    


    3년 전
1개의 댓글이 있습니다.
  • WeissBlume
    WeissBlume

    struct Comparator {
    const vector& group;
    const int t;
    Comparator(const vector &group, int t):
    group(group), t(t) {}
    // 생략
    };

    reference 변수는 반드시 생성과 동시에 초기화돼야 합니다.
    따라서 = 연산자로 대입하는 게 아니라 위와 같이 생성자에 넣어줘야 합니다.


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