zxkyh100   6년 전

비쥬얼 스튜디오에서는 잘 돌아가는데 서버에서는 런타임 오류가 납니다ㅜㅜ

어디서 오류가나는지 알 수 가 없어서 이렇게 질문 올려요

#include <stdio.h>

void quick_sort(int *arr, int start, int end);
void swap(int *a, int *b);

int main() {
int n;
scanf("%d", &n);

int *arr;
arr = (int *)malloc(sizeof(int)*n);

for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

int sum = 0;

for (int i = 0; i < n; i++) {
sum += arr[i];
}

quick_sort(arr, 0, n - 1);

printf("%.0f\n", (double)sum / n); // 평균을 구함
printf("%d\n", arr[n / 2]); // 중간값을 구함

int *val_arr;

val_arr = (int*)calloc(n,sizeof(int)); 
//calloc 을 사용하면서 동적할당을 하면서 초기화를 진행

int val_n = 1;

val_arr[0] = arr[0]; // val = 최대빈도수의 값 배열

int max = 1, fre_n = 1; // max = 최대 빈도수, n = 현재 빈도수

for (int i = 1; i < n; i++) {
if (arr[i] == arr[i - 1])
{
fre_n++;
}
else {
if (fre_n > max) {
max = fre_n;
for (int j = 0; j < val_n; j++) {
val_arr[j] = 0;
}
val_arr[0] = arr[i-1];
val_n = 1;
fre_n = 1;
}
else if (fre_n == max) {
val_arr[val_n] = arr[i];
val_n++;
}
else {
fre_n = 1;
}
}
}

if (val_arr[1] != 0) {
printf("%d\n", val_arr[1]);
}
else {
printf("%d\n", val_arr[0]);
}

printf("%d", arr[n - 1] - arr[0]);

}

void quick_sort(int *arr, int start, int end) {
if (start > end) return;

int mid = (start + end) / 2;
int pivot = arr[mid];

swap(&arr[start], &arr[mid]);

int p = start + 1;
int q = end;

while (1)
{
while (arr[p]<=pivot)
{
p++;
}
while (arr[q]>pivot)
{
q--;
}

if (p > q) break;

swap(&arr[p], &arr[q]);
}

swap(&arr[start], &arr[q]);
quick_sort(arr, start, q - 1);
quick_sort(arr, q + 1, end);
}

void swap(int *a, int *b) {
int tmp = *a;
*a = *b;
*b = tmp;
}

djm03178   6년 전

퀵소트를 직접 구현할 때 나타날 수 있는 오류인데요,

일반적인 퀵소트 알고리즘의 경우 최악의 경우 재귀호출이 엄청나게 깊어질 수 있는데, 이를 런타임 에러로 처리하는 것으로 보입니다.

물론, 재귀로 구현하지 않는다고 해도 이런 경우라면 시간초과가 되겠지요.

이럴 때는 stdlib.h의 qsort를 쓰시면 됩니다.

zxkyh100   6년 전

감사합니다!! 런타임 오류를 해결 할 수 있었습니다.

질문 한가지만 더 드리자면 그럼 실제로 qsort를 구현하는것보다 라이브러리의 qsort를 사용하는게 속도적인 측면에서도 더 빠른건가요??

djm03178   6년 전

qsort의 정확한 구현 방법에 대해서는 표준에서 정의하고 있지 않지만 (표준에는 qsort의 최악의 수행 시간이 n lg n 이어야 한다는 말도 없습니다), 적어도 백준 채점 서버에서 qsort는 상당히 빠른 속도로 잘 돌아갑니다. 한 가지 아쉬운 점이 있다면, 비교 연산을 전부 커스텀 함수를 호출해서 하기 때문에 C++의 std::sort보다는 어쩔 수 없이 느리다는 것이지만, 그럼에도 불구하고 평균 / 최악의 시간 모두 제법 훌륭한 편이라고 느끼고 있습니다.

댓글을 작성하려면 로그인해야 합니다.