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 |