[ZEROONE] 문제에 대해서 궁금한게 있습니다!!

  • ntinamu
    ntinamu
     #include <stdio.h>
    
    #include <stdlib.h>
    
    int main(){
    
        int n,i,j,q[1000000];
    
        char t1,t2,p[1000001];
    
        scanf("%s",p);
    
        q[0]=0;
    
        for(i=0,j=1;p[j];j++){
    
            if(p[i]!=p[j]) i=j;
    
            q[j]=j-i;
    
        }
    
        scanf("%d",&n);
    
        while(n--){
    
            scanf("%d%d",&i,&j);
    
            if(q[(i>j)?i:j]>=abs(i-j)) printf("Yes\n");
    
            else printf("No\n");
    
        }
    
        return 0;
    
    }
    

    이것은 시간초과 안된 패스된 코드입니다.

    이 코드의 문제풀이 의도는 수열의 길이만큼 새로운 메모리를 캐쉬로 사용해서 자신의

    수와 똑같은 수가 자신의 위치를 기준으로 왼쪽에 연속으로 몇개를 사용하는지 저장합니다.

    이렇게하면 O(n)의 시간복잡도로 문제를 풀 수 있는걸 이해할 수 있습니다.

     #include <iostream> 
    
    #include <stdio.h> 
    
    
    
    using namespace std; 
    
    
    
        unsigned int ar[1000001]; 
    
        char input[1000003]; 
    
    int main(void){ 
    
            int count = 0; 
    
            int k = 0; 
    
            scanf("%s", input); 
    
            ar[0] = count; 
    
            while(input[++k] != NULL){ 
    
                if(input[k-1] != input[k]) 
    
                    count++; 
    
                ar[k] = count;     
    
            } 
    
    
    
            int caseNum; 
    
            cin >> caseNum; 
    
            while(caseNum--){ 
    
                int t1, t2; 
    
                cin >> t1 >> t2; 
    
                if(ar[t1] == ar[t2]) 
    
                    cout << "Yes" << endl; 
    
                else 
    
                    cout << "No" << endl; 
    
            } 
    
    
    
        return 0; 
    
    } 
    

    이것은 시간초과가 나는 코드입니다. 자신의 전 위치와 자기 자신이 같은지 비교여부를

    캐시메모리에 저장하는데요. 이것도 제가 보기에는 O(n)으로 위의 알고리즘과 성능 차이가

    보기에는 없어보이는데 시간초과가 나네요 ㅠㅠ

    제가 보기에는 비슷한 성능의 알고리즘이긴 한데 테스트케이스의 종류에 따라 성능이 달라진거 같긴한데

    제 생각이 맞는지 궁금해서 여쭤봅니다. ㅠㅠ


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