ZEROONE 문제 좀 도와주세요 ㅠ

  • aozo
    aozo

    ZEROONE 문제 풀고 있습니다.
    위와 같이 작성하였는데, 시간 초과로 나오네요.

    접근한 방법은 주어진 char 배열을 0 또는 해당 배열의 최대 값인지
    비교 하여 맞다면 yes 아니면 no 라는 생각으로 작성하였습니다.
    알고리즘의 복잡도가 반복문이 최소 1번은 들어가야 하고 ( 문제 입력수) 이후 제가 쓴부분은 1번인데, 이것마저도 없애야 하는 정도로 최적화 해야 한다면 정답에 대한 접근법을 다시 생각해야 겠군요.

    결론은 제가 만든 for 문이 1번도 들어가면 시간초과가 되는건지 아니면
    로직에 문제가 있는 건지 궁금합니다. ㅠ_ㅠ 헬푸요.

    #define _CRT_SECURE_NO_WARNINGS
    
    #include<stdio.h>
    
    void swipe(int *start, int *end);
    
    int main() {
    
        char inputString[1000000+1] = "0";
        scanf("%s", inputString);
    
        int testcount = 0;
        scanf("%d", &testcount);
    
        int start = -1;
        int end = -1;
        if (testcount > 100000)
            testcount = 100000;
    
        if (testcount >= 0){
            while (testcount--) {
                scanf("%d %d", &start, &end);
                if (start < 0)
                    start = 0;
                if (end > 1000000)
                    end = 1000000;
    
                swipe(&start, &end);
    
                int result = 0;
                int binary = 1;
    
                // 1) char 를 2진수로 변경 후 다시 10 진수로 변경
                for (int i = end ; i >= start; i--)
                {
                    if (inputString[i] == '1')
                    {                   
                        result += binary;
                    }
                    binary = binary << 1;
    
                }
    
                // 2) 입력된 자릿수의 최대 int 값을 만듦
    
                int max = 1;
    
                max = binary - 1;
    
                // 3) 0 또는 최대 값과 비교
    
                if ( result == 0 || result == max)
                    printf("Yes\n");
                else
                    printf("No\n");
            }
        }
        return 0;
    }
    
    void swipe(int *start, int *end)
    {
        int temp = *end;
        if (*start > *end)
        {
            *end = *start;
            *start = temp;
        }
    }
    

    10년 전
5개의 댓글이 있습니다.
  • Being
    Being

    네, 이렇게 하시면 시간 안에 나오지 않습니다.


    10년 전 link
  • aozo
    aozo

    그렇군요 다시 한번 해보겠습니다.
    답변 감사드려요~!:D


    10년 전 link
  • aozo
    aozo

    ㅎ 이제 보니 문제를 잘못이해 하고 있었군요
    가운데 구간은 무시하고 i j 로 선택된 녀석들만 두개를 1,1 인지 0, 0 인지
    비교하는 루틴이 필요하군요 하핫


    10년 전 link
  • aozo
    aozo

    그러면 1001 입력에서 (0, 3) 이라고 할 경우
    Yes 인가요 No 인가요?


    10년 전 link
  • Being
    Being

    No 입니다.


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