(알고리즘) 알고스팟 ZeroOne

알고스팟 (https://algospot.com)에서 처음으로 풀어본 문제

초보문제라는데 어려웠다

그냥 반복문을 n번(수열길이)만큼 돌려도 될거라고 생각했었는데

수행시간이 계속 초과 되어 int형 배열을 이용해  그룹화 하여

비교할때 바로 비교 할 수 있게 하니 확실히 시간이 많이 단축되었다.

/////////////////////////////////////////////////////////////////////////////////////

문제

0과 1로 구성된 수열이 있다. 수열의 길이가 N이라 하고, 각각의 수열의 원소마다 순서대로 번호를 매길 경우 첫 번째 숫자는 0번이 되고 두 번째 숫자는 1번, 그리고 마지막 숫자는 N-1이 된다. 임의적으로 0이상 N-1이하의 2개의 숫자 i,j를 잡고 i번째부터 j번째 까지의 숫자 중에서의 최대값과 최소값을 찾아서 두 값이 일치하는지 알아보고자 한다.

입력

첫 번째 줄에는 최대 길이 1,000,000의 수열이 들어온다. 수열의 사이에는 빈칸이 없다. 그 다음 줄에는 질문의 개수를 뜻하는 정수 N(N<=100,000)이 입력된다. 그 다음줄부터 해당구간 i,j를 의미하는 2개의 숫자가 N개의 줄로 입력된다.

출력

각각의 질문의 순서대로 해당구간 i,j의 최대값과 최소값이 같을 경우 Yes를, 그렇지 않을 경우는 No를 출력한다.

예제 입력

0000011111
3
0 5
4 2
5 9

예제 출력

No
Yes
Yes

소스

/////////////////////////////////////////////////////////////////////////////////////

#include <stdio.h>

int main(){

     char input[1000001];

     int grpIn[1000001];

     

     int i=0;

     int j=0;

     int N=0;

     int A=0;

     int num=0;

     

     scanf("%s", input);

     scanf("%d", &N);

     

     for(A=0; A<1000001; A++){

         if(input[A] == '\0') break;

         

         grpIn[A] = num;  

         if(input[A] != input[A+1]){

              num++;            

         }              

     }

     

     while(N){

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

              

         if(grpIn[i] == grpIn[j]) printf("Yes\n");

         else printf("No\n");

         N--;                          

     }

}

/////////////////////////////////////////////////////////////////////////////////////