ZEROONE_알고리즘

1. 무식하게 풀기

생각

1단계. 먼저 0, 1로 이루어진 수열을 배열에 입력받는다.

2단계. 두개의 인덱스A, B를 입력받는다.

3단계. 함수 bool f(int A, int B)를 호출

함수 내용 

- 배열의 A번째부터 B까지 순차적으로 비교

- 비교 중 A번째 인덱스에 들어있는 값과 다르면 false 리턴

코드

#include <iostream>
// 백만
static const int MAX = 1000000;
char g_ZeroOneArr[MAX + 1] = {0, };
bool f(int indexA, int indexB);
 
int main(void)
{
    // 입력되는 두 수
    int indexA, indexB = 0;
    // 테스트 케이스
    int testCase = 0;
    scanf("%s", g_ZeroOneArr);
    scanf("%d", &testCase);
    
    while(testCase--){
        // 두 수 입력
        scanf("%d %d", &indexA, &indexB);
 
        // 오름차순 정렬
        if(indexA > indexB)
        {
            int temp = indexA;
            indexA = indexB;
            indexB = temp;
        }
        
        // (모두 1 or 모두 0) == YES
        if(f(indexA, indexB))
            printf("Yes\n");
        else
            printf("No\n");
    }
}
// 함수 구현
// 인덱스 A ~ B까지 반복 하며 중간에 값이 변하면 FALSE
bool f(int indexA, int indexB)
{
    for(int i = indexA; i <= indexB; i++)
    {
        if(g_ZeroOneArr[i] != g_ZeroOneArr[indexA])
        {
            return false;
        }
    }
    return true;
}
 
 
 Colored by Color Scripter

출력

1111100000
 
5
1 0
Yes
1 1
Yes
4 5
No
5 4
No
0 9
No

위와같이 출력되는것을 알수 있다. 

하지만 위의 코드를 문제 풀이 사이트에 제출하면 [TimeOut] 이 되어버린다.

좀더 빠른 코드를 짜야한다.

먼저 위의 코드는 아래와 같은 최악의 경우

0000000....1(N = 100만)

indexA = 0, indexB = 999999

테스트 케이스 10만

100만 * 10만 의 for문을 반복한다.

2. 배열에 기록하기

생각

1단계. 먼저 0, 1로 이루어진 수열을 배열에 입력받는다.

2단계. 배열을 0 ~ N 까지 반복하면서 i값을 기록한다. (i는 0부터 시작)

          - if( arr[N] != arr[N -1] ) 라면 i 값을 1더하여 기록

3단계. 함수 bool f(int A, int B)를 호출

함수 내용 

- 배열의 A번째 원소와 B번째 원소의 값이 서로 다르면 false 같으면 true 반환

코드

// ZEROONE_2
#include <iostream>
 
// 백만
static const int MAX = 1000000;
// 수열 배열
char g_ZeroOneArr[MAX + 1] = {0, };
// 기록 배열
int g_CheckFlagArr[MAX + 1] = {0, };
bool f(int indexA, int indexB);
 
int main(void)
{
    // 입력되는 두 수
    int indexA, indexB = 0;
    // 테스트 케이스
    int testCase = 0;
    // 수열의 길이
    unsigned long stringLength = 0;
    unsigned int checkFlag = 0;
    
    scanf("%s", g_ZeroOneArr);
    scanf("%d", &testCase);
    stringLength = strlen(g_ZeroOneArr);
    
    // 체크 플래그 설정
    // i번째 요소와 i-1번째 요소가 서로 다르면 check + 1
    for(int i = 1 ;i < stringLength; i++)
    {
        if(g_ZeroOneArr[i-1] != g_ZeroOneArr[i])
            checkFlag++;
        g_CheckFlagArr[i] = checkFlag;
    }
    
    while(testCase--){
        // 두 수 입력
        scanf("%d %d", &indexA, &indexB);
        
        // (모두 1 or 모두 0) == YES
        if(f(indexA, indexB))
            printf("Yes\n");
        else
            printf("No\n");
    }
}

출력

1010101100
5
1 2
No
2 1
No
1 1 
Yes
2 4
No
4 5
No

딱히 어려운 부분은 없으므로 설명은 생략하고 for문 횟수를 보면 

처음에 최대 100만번을 반복하고 그후에는 반복이 없는 것을 알수 있다.

즉 100만 + 10만 최대 110만 번 반복,  이전의 알고리즘보다 매우 빠른 속도를 낼 수 있다는것을 알 수 있다. 

문제풀이 사이트에 제출하니 (실행시간 241ms) 정답을 받을 수 있었다.