zeroone 알고리즘에 대해 질문이 있습니다.

  • suhee
    suhee

    아래는 제가 작성한 코드입니다. 제가 제출했던 이전답안들을 보시면 아시겠지만 기존 제 방식으로는 계속 시간초과가 떠서,
    (제 풀이법은 입력받은 수열이 0->1 또는 1->0으로 변하는 구간값을 배열에 저장하고 입력받은 i,j의 차가 구간의 차이보다 작을 때 통과되는 방식을 사용하였습니다)
    그래서 질문과 답변 게시판에서 제출에 성공한 코드를 찾아서 같은방식으로 기존 제 알고리즘을 수정해 제출해보았습니다.
    (참고한 링크 http://algospot.com/forum/read/1255/)

    궁금한 점은, 알고리즘이 같은데 제 코드는 시간초과가 뜨고, 윗 링크의 코드는 정답이 뜬다는 점입니다.
    아직 c언어 초보라 링크의 작성자분과 제 코드의 다른 작성부분에서(gets라던지 define..?) 시간초과의 원인이 발생한 것 같은데
    설명좀 부탁드릴 수 있을까요?
    만약 이런부분에서 시간초과가 발생하는거였고 그 원인을 안다면, 지금 시간초과로 막힌 다른 문제들을 푸는데 큰 도움이 될 것 같습니다.
    감사합니다.

    #include <stdio.h>
#include <string.h>

int main()
{

    char input[1000001] = {};
    int distance[1000001] = {};

    int i,j; // 구간
    int c,k,l; //for문용 변수
    int test_case;
    int n = 0;

    char v = NULL;

    gets(input);

    for(c=0; c<strlen(input); c++){

        if(input[c] != v){
            v = input[c];
            n++;
        }
        distance[c] = n;
    }

    scanf("%d", &test_case);

    for(k=0; k<test_case; k++){

        scanf("%d %d", &i, &j);

        if(distance[i] == distance[j]){
            printf("Yes\n");
            }

        else{
            printf("No\n");
        }

    }

    return 0;

}

    9년 전
3개의 댓글이 있습니다.
  • Being
    Being

    자주 하는 실수 모음 페이지에 항목이 있기는 한데, 아직 채워지지 않은 부분이네요. "for(A; B; C)의 B에서 strlen 사용하기" 항목에 걸린 링크를 참고해 보시기 바랍니다.


    9년 전 link
  • Being
    Being

    다음부터 코드를 올리실 때는 양식에 맞춰 작성해주시기를 부탁드립니다. 제가 글을 수정하였으니 참고하시기 바랍니다.


    9년 전 link
  • suhee
    suhee

    아, strlen 때문이었군요. 답변 감사드립니다.
    글작성이 처음이라 양식도 실수했네요. 죄송합니다. 다음부턴 양식에 맞추겠습니다! 늦은시간에도 고생많으십니다!


    9년 전 link

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