글 읽기 - 왜 런타임에러가 나는지 모르겠습니다...

hnryu 6년 전 0

런타임 에러가 나는 이유를 모르겠습니다...

#include<stdio.h>
#include<stdlib.h>

int compare(void *first, void *second);
int main(void)
{
	int n;
	int *arr;

	scanf("%d", &n);
	arr = (int *)malloc(sizeof(int)*n);
	int i, j;

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

	qsort(arr, n, sizeof(int), compare);

	for ( j = 0; j < n; j++) {
		printf("%d\n", arr[j]);
	}
}
int compare(void *first, void *second)
{
	if (*(int*)first > *(int*)second)
		return 1;
	else if (*(int*)first < *(int*)second)
		return -1;
	else
		return 0;
}

bupjae 6년 전 1

이 프로그램의 메모리 제한은 8MB 인데, n이 1000만에 가까울 때 11번째 줄에서 약 38MB 의 메모리를 할당받으려고 합니다.

메모리가 부족하기 때문에 malloc 는 NULL을 반환하고, 이후에 arr에 무언가를 쓰려고 할 때 런타임 에러가 발생합니다.

이 문제는 시간복잡도 O(n log n) / 공간복잡도 O(n) 으로는 시간 제한 및 메모리 제한을 만족시킬 수 없습니다.

입력 데이터가 특정한 조건을 만족시킬 때 사용할 수 있는 시간복잡도 O(n) / 공간복잡도 O(1) 인 Counting Sort 정렬 알고리즘이 있습니다. 이 쪽을 공부해 보세요.

hnryu 6년 전 0

조언 주신데로 counting sort 정렬 알고리즘 나름대로 이해하여 코드를 구현하였습니다.

코드가 잘못된것인지 아직 이해가 부족한것인지 런타임에러가 계속 출력되어서요. 다시한번 조언구합니다.

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 10000000
int main(void)
{

	int n;
	int sort[10000] = { 0, };
	int arr[MAXSIZE] = { 0, };
	int cntsort[MAXSIZE] = { 0, };
	
	scanf("%d", &n);
	
	int i, j=0;

	for (i = 0; i < n; i++) {
		scanf("%d", &arr[i]);	// index 입력
		sort[arr[i]]++;			// 해당 index의 반복횟수 
	}
	for (i = 0; i < MAXSIZE; i++) {
		while (sort[i]> 0) {
			cntsort[j] = i;
			sort[i]--;
			n--;
			printf("%d\n", cntsort[j]);
			j++;
		}
		if (n == 0) break;
	}
}

bupjae 6년 전 1

counting sort 를 올바로 구현했다면 MAXSIZE 배열을 잡을 필요가 없어집니다.

조금만 더 고민해 보세요.

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

문제

문제

출처

ICPC

왜 런타임에러가 나는지 모르겠습니다...

hnryu 6년 전 0

bupjae 6년 전 1

hnryu 6년 전 0

bupjae 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말