ZEROONE 해결 방법 질문드립니다. tyjk32 ZEROONE 문제에서 제 생각은 배열의 해당 범위만을 MergeSort 해서 맨앞과 맨뒤의 값만을 비교하여 다르면 No, 같으면 Yes가 나오도록 했습니다. 그런데 계속 시간초과가 나오던데, 방법이 잘못된 것인지 소스코드에 문제가 있는 것인지 해결 방법에 대한 조언좀 부탁드리겠습니다. #include <stdio.h> #include <string.h> #define MIN(X,Y) ((X) < (Y) ? (X) : (Y)) #define MAX(X,Y) ((X) > (Y) ? (X) : (Y)) void merge(char *arr, char *arr2, int low, int mid, int high); void mergeSort(char *arr, char *arr2, int low, int high); int main(void) { char arr[1000001], arr2[1000001]; int n, i, j; int a, b; scanf("%s %d", arr, &n); for(a = 0; a < n; a++) { memset(arr2, 0, 1000001); scanf("%d %d", &i, &j); mergeSort(arr, arr2, MIN(i, j), MAX(i, j)); if(arr2[0] != arr2[j - i]) { printf("No\n"); } else { printf("Yes\n"); } } return 0; } void mergeSort(char *arr, char *arr2, int low, int high) { int mid; if(low < high) { mid = (low + high) / 2; mergeSort(arr, arr2, low, mid); mergeSort(arr, arr2, mid + 1, high); merge(arr, arr2, low, mid, high); } } void merge(char *arr, char *arr2, int low, int mid, int high) { int i = low; int j = mid + 1; int k = low; while(i <= mid && j <= high) { if(arr[i] < arr[j]) { arr2[k++] = arr[i++]; } else if(arr[i] >= arr[j]) { arr2[k++] = arr[j++]; } } } 10년 전
2개의 댓글이 있습니다. 일루 방법의 문제입니다. 최대 100만개 정렬을 10만번 한다는 건데 시간제한에 걸립니다. 10년 전 link tyjk32 아 방법을 다시생각해봐야겠네요..감사합니다 ^^ 10년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
tyjk32
ZEROONE 문제에서 제 생각은 배열의 해당 범위만을 MergeSort
해서 맨앞과 맨뒤의 값만을 비교하여 다르면 No, 같으면 Yes가
나오도록 했습니다.
그런데 계속 시간초과가 나오던데, 방법이 잘못된 것인지 소스코드에
문제가 있는 것인지 해결 방법에 대한 조언좀 부탁드리겠습니다.
10년 전