코드 리뷰 부탁드려도 될까요?

Question

#include <stdio.h> #pragma warning(disable:4996) typedef struct { int a; int a2; }test2; void arr(test2* a, int n2, int n) { int i, i2, cnt; cnt &#61; 0; int cnt2 &#61; n; test2 t; for(i2&#61;0; i2<n; i2&#43;&#43;) { if (n2 &#61;&#61; 0) { for (i &#61; 0; i < n; i&#43;&#43;) { for (int j &#61; 0; j < cnt2; j&#43;&#43;) { if (i !&#61; j) { if (a[i].a < a[j].a) { break; } cnt&#43;&#43;; } } if (cnt !&#61; cnt2 - 1) { cnt &#61; 0; continue; } t &#61; a[i]; a[i] &#61; a[cnt2-1]; a[cnt2-1] &#61; t; cnt2--; cnt &#61; 0; } } else if(n2&#61;&#61; 1) { for (i &#61; 0; i < n; i&#43;&#43;) { for (int j &#61; 0; j < cnt2; j&#43;&#43;) { if (i !&#61; j) { if (a[i].a2 < a[j].a2) { break; } cnt&#43;&#43;; } } if (cnt !&#61; cnt2 - 1) { cnt &#61; 0; continue; } t &#61; a[i]; a[i] &#61; a[cnt2 - 1]; a[cnt2 - 1] &#61; t; cnt2--; cnt &#61; 0; } } } } int main() { test2 a[50000] &#61; {0, }; int n &#61; 0; int i &#61; 0; scanf(&#34;%d&#34;, &n); for (i &#61; 0; i < n; i&#43;&#43;) { scanf(&#34;%d&#34;, &a[i].a); a[i].a2 &#61; i; } arr(a, 0, n); for (i &#61; 0; i < n; i&#43;&#43;) { a[i].a &#61; i; } arr(a, 1, n); for (i &#61; 0; i < n; i&#43;&#43;) { printf(&#34;%d &#34;, a[i].a); } return 0; }https://codeup.kr/problem.php?id&#61;3004이 문제에 대한 제 코드인데, 초기 아이디어는 이렇습니다.멤버변수a에 각 수들을 입력하고 a2에 배열 번호에 따라 순서를 매긴 뒤 멤버변수 a에 대해 구조체 배열 a를 정렬하여 a2에 각 수들의 대소관계 순서에 대한 정보를 입력합니다.그 다음에 멤버변수 a에 다시 배열 번호에 따라 0부터 n-1까지 차례대로 순서를 매기고, a2에 대해 a를 재정렬합니다. 그리고 a를 출력하면 재정렬된 a가 나타난다고 생각했습니다.그러나 예시의 입력에 대해 2 0 3 1 4가 아니라 다른 수가 출력되는데, 정렬과정에서 앞뒤로 교체할 때 문제가 있는 것인가요?

bot99 · Accepted Answer

제가 다음의 온라인 컴파일러에서 시험해본 바로는 주어진 입력값에 대해서는 제대로 2 0 3 1 4가 출력이 됩니다. 코드업에 해당 코드를 올려봐도 시간 초과로만 나오고요. 코드를 다 뜯어보지는 않았지만 설명하신 알고리즘도 타당해 보이고, 문제는 정렬 알고리즘이 너무 느려서 시간이 초과되는게 아닌가 합니다.https://www.onlinegdb.com/online_c_compiler일단, 93번째 행을 다음과 같이 고쳐야 합니다. 그렇게 하지 않아도 결과는 나오겠지만... scanf("%d", &a[i].a);O 표기법으로는 어차피 같은 등급이겠지만, 정렬을 두번 하는 것보다는 한번 하여 순서대로 나열한 인덱스 값을 구한 다음에 그 인덱스의 역을 구하는 것이 시간이 거의 반으로 줄어듭니다. 참고로 저는 정렬에는 표준 라이브러리의 qsort 함수를 썼습니다.#include #include #define MAX_ARR_SIZE 50000 int inputArr(int * arr, int * arr_idx, int arr_size) { int i; for ( i = 0; i < arr_size; ++i ) { scanf("%d", arr + i); arr_idx[i] = i; } return 0; } int compArrIdx(const void *pa, const void * pb) // compArrIdx(arr, 0); <- arr 포인터의 초기화 // compArrIdx(0, arr_idx); <- arr_idx 포인터의 초기화 { int ia; int ib; static int * arr = NULL; static int * arr_idx = NULL; if ( pb == NULL ) { arr = (int *)pa; return 0; } else if ( pa == NULL ) { arr_idx = (int *)pb; return 0; } ia = (int *)pa - arr_idx; ib = (int *)pb - arr_idx; if ( arr[arr_idx[ia]] < arr[arr_idx[ib]] ) { return -1; } else if ( arr[arr_idx[ia]] > arr[arr_idx[ib]] ) { return 1; } return 0; } void invertArr(int * arr, int * inverse_arr, int size) { int i; for ( i = 0; i < size; ++i) { inverse_arr[arr[i]] = i; } } void printArr(int * arr, int size) { int i; printf("%d", arr[0]); for ( i = 1; i < size; ++i ) { printf(" %d", arr[i]); } printf(" "); return; } int main() { int arr[MAX_ARR_SIZE]; int arr_idx[MAX_ARR_SIZE]; int inverse_arr_idx[MAX_ARR_SIZE]; int arr_size; scanf("%d", &arr_size); if ( arr_size > MAX_ARR_SIZE ) { printf("ERROR: Too big number! (N < %d) ", MAX_ARR_SIZE); } inputArr(arr, arr_idx, arr_size); // compArrIdx 함수의 정적 내부 변수에 배열과 인덱스 배열의 포인터 저장 compArrIdx(arr, 0); compArrIdx(0, arr_idx); // 인덱스 별로 정렬 qsort(arr_idx, arr_size, sizeof(*arr_idx), compArrIdx); // 정렬된 인덱스의 역을 구함 invertArr(arr_idx, inverse_arr_idx, arr_size); // 출력 printArr(inverse_arr_idx, arr_size); return 0; }

코드 리뷰 부탁드려도 될까요?

1개의 답변

Q&A 목록