1. 무식하게 풀기


생각

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

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

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

함수 내용 

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

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


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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;
}
 
 
cs
 

출력

1
2
3
4
5
6
7
8
9
10
11
12
13
1111100000
 
5
1 0
Yes
1 1
Yes
4 5
No
5 4
No
0 9
No
cs


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

하지만 위의 코드를 문제 풀이 사이트에 제출하면 [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 반환


코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// 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");
    }
}
cs


출력

1
2
3
4
5
6
7
8
9
10
11
12
1010101100
5
1 2
No
2 1
No
1 1 
Yes
2 4
No
4 5
No
cs


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

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

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

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

'All > Algorithm' 카테고리의 다른 글

BOGGLEGAME_알고리즘_3  (0) 2015.12.28
BOGGLEGAME_알고리즘_2  (0) 2015.12.28
BOGGLEGAME_알고리즘_1  (0) 2015.12.28
BOGGLEGAME_문제  (0) 2015.12.28
ZEROONE_문제  (0) 2015.12.28

이번에 푼 알고리즘문제는 ZEROONE이라는 문제이다.

먼저 문제를 보면 아래와 같다.



문제

 

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

노트

 

0,5 : 000001 -> 최대값 : 1, 최소값 : 0
4,2 : 000 -> 최대값 : 0, 최소값 : 0
5,9 : 11111 -> 최대값 : 1, 최소값 : 1


요약하면

1. 0또는 1로 이루어진 수열 (0101010101... 최대 100만 ) 이 입력됨

2. 각각의 원소는 0부터 차례로 인덱스를 가짐 

3. 임의의 2개의 인덱스를 입력 받음

4. 두 인덱스사이의 값이 모두 0또는 모두 1이면 Yes출력 아니면 No출력

최대 10만번의 테스트를 2000ms (2초) 안에 수행해야한다.

 *문제 출저 알고스팟


'All > Algorithm' 카테고리의 다른 글

BOGGLEGAME_알고리즘_3  (0) 2015.12.28
BOGGLEGAME_알고리즘_2  (0) 2015.12.28
BOGGLEGAME_알고리즘_1  (0) 2015.12.28
BOGGLEGAME_문제  (0) 2015.12.28
ZEROONE_알고리즘  (0) 2015.12.28

+ Recent posts