글 읽기 - 메모리 초과가 됩니다...ㅠㅠ

loverdevelop15 4년 전 0

퀵소트로 동적할당하여 문제를 풀었는데 자꾸 메모리 초과가 뜨네요...

어떻게 해결하면 좋을까요??

//quickSort 이용한 k번째 수 찾기
//k-1인덱스까지만 정렬하면 됨.

#include <stdio.h>
#include <stdlib.h>
const long long int MAX = 5000000;

int getLeft(long long int arr[], int s, int e, int pivot, long long int result[]) {
	int inx = 0;
	for (int i = s; i <= e; i++) {
		if (arr[i] <= pivot) {
			result[inx++] = arr[i];
		}
	}
	return inx;
}
int getRight(long long int arr[], int s, int e, int pivot, long long int result[]) {
	int inx = 0;
	for (int i = s; i <= e; i++) {
		if (arr[i] > pivot) {
			result[inx++] = arr[i];
		}
	}
	return inx;
}
void quickSort(long long int arr[], int start, int end) {

	if (start >= end) return;
	
	int pivot = arr[start];
	long long int* left;
	long long int* right;

	left = (long long int*)malloc(sizeof(long long int*)* MAX);
	right = (long long int*)malloc(sizeof(long long int*)* MAX);

	int left_cnt = getLeft(arr, start + 1, end, pivot, left);
	int right_cnt = getRight(arr, start + 1, end, pivot, right);

	for (int i = 0; i < left_cnt; i++) {
		arr[start + i] = left[i];
	}

	arr[start + left_cnt] = pivot;

	for (int i = 0; i < right_cnt; i++) {
		arr[start+left_cnt+1+i] = right[i];
	}

	quickSort(arr, start, start+left_cnt-1);
	quickSort(arr, start+left_cnt+1, end);
}

int main() {
	long long int n, k;
	scanf("%lld", &n);
	scanf("%lld", &k);

	long long int* arr = (long long int *)malloc(sizeof(long long int) * MAX);
	for (int i = 0; i < n; i++)
		scanf("%lld", &arr[i]);
		
	quickSort(arr, 0, k);

	printf("%lld", arr[k-1]);

	return 0;
} 

chogahui05 4년 전 0

quick sort의 depth가 깊어지는 경우 메모리 초과가 납니다.

seico75 4년 전 0

우선 +/-10^9 은 long 형이면 충분합니다.

2. left, right 를 따로 메모리 할당을 받는 것은 일반적이지 않은 것 같습니다.

보통 퀵소트에서는 추가 메모리 할당 없이 처리를 합니다.

3. 내부에서 할당을 하시겠다고 하면 end-start 크기면 되지 않을까 합니다.

그리고 다 쓰고 나서 free 를 안하시네요. main 에서도 마찬가지고..

malloc free 페어를 맞추는 습관이 없으면 나중에 대재앙을 경험하실 지도 모릅니다.

4. 이 문제는 전체 quick 소트하면 시간초과 날지도 모릅니다. 일단 메모리 문제 확인하고 나서 시간초과나면 더 고민해보시는 것도 좋겠습니다.

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

문제

문제

출처

ICPC

메모리 초과가 됩니다...ㅠㅠ

loverdevelop15 4년 전 0

chogahui05 4년 전 0

seico75 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말