PALINDROMIZE 시간초과를 피할수가없습니다 ㅠㅠ

  • westwoods
    westwoods
    #include<iostream>
    #include<string.h>
    using namespace std;
    
    static char a[100001];
    static char last;
    static int point[100001];
    static int N;
    void serch(int len, int end)
    {
        N = 0;
        for (int i = end; i < len ; i++)
        {
            if (last == a[i] && a[len-1 ] == a[i+1])
            {
                point[N] = i;
                N++;
            }
        }
        point[N] = len;
    
    }
    
    int boolen(int len, int ary)
    {
        if (len == point[ary]||N==0 ) {
            return 1;
        }
    
        for (int i = 3; i <= (len - point[ary])/2; i+=2)
        {
            if (a[len - i] != a[point[ary] + i]|| a[len - i-1] != a[point[ary] + i+1])
                return 0;
        }
        return 2;
    
    }
    int main()
    {
        ios::sync_with_stdio(false);
    
        int A,temp,len,number;
    
        cin >> A;
        while (A--)
        {
            cin >> a;
            temp = 0;
            len = strlen(a) - 1;
            last = a[len];
            serch(len, 0);
            if(N==0)
                cout << len * 2 + 1 << "\n";
    
            for (number = 0; number < N; number++)
            {
                int l = boolen(len, number);
                if (l>0)
                {
                    if (l == 2)
                    {
                        cout << len + point[number] + 1 << "\n";
                        break;
                    }
                    if (l== 1)
                    {
                        cout << len * 2 + 1 << "\n";
                        break;
                    }
                }
            }
            if(number==N&&N!=0)
                cout << len * 2 + 1 << "\n";
    
    
        }
    }
    

    알고리즘은 맨뒤에문자와 같은 문자가있는 위치를 point에 저장한후 boolen 함수를 통해서 맨뒤 문자와 똑같은 문자 사이에있는 문자들이 완전히 일치하는지 확인하고 모두 일치하면 포문을 탈출하고 일치하지않으면 point에 들어있는 그 다음 맨뒤문자와 같은 문자부터 같은 작업을 반복합니다. 이때 모든 point에 대해서 만족하지않으면 최대길이로 계산이됩니다.

    문제는 재귀로 파고드는것도아니고 포문도 2중포문 정도인듯한데 시간초과나는 이유가 무엇일지요?


    9년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    n이 10만인데 2중포문이면 당연히 시간초과가 납니다. ^^;


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