글 읽기 - 머지소트 런타임 에러

qkrguswndk 6년 전 0

여러개 돌려봤는데 값은 잘 나오는데

백준에 넣으면 런타임 에러가 뜹니다..ㅠ

#include <stdio.h>
#include <malloc.h>

int *S;

void merge2(int low, int mid, int high) {
	int i = low, j = mid + 1, k = low;

	int * U = (int *)malloc(sizeof(int)*(high - low + 1)*2);

	while (i <= mid && j <= high) {
		if (S[i] < S[j]) {
			U[k] = S[i];
			i++;
		}
		else {
			U[k] = S[j];
			j++;
		}
		k++;
	}
	//남은거 복붙
	while (i <= mid) {
		U[k] = S[i];
		i++, k++;
	}

	while (j <= high) {
		U[k] = S[j];
		j++, k++;
	}
	//다시 S로
	for (int t = low; t <= high; t++) {
		S[t] = U[t];
	}
}

void mergesort2(int low, int high) {
	int mid;
	if (low < high) {
		mid = (low + high) / 2;
		mergesort2(low, mid);
		mergesort2(mid + 1, high);

		merge2(low, mid, high);
	}
}

int main() {
	int n;
	scanf("%d", &n);
	S = (int *)malloc(sizeof(int) * n*2);
	for (int i = 0; i < n; i++)
		scanf("%d", &S[i]);
	mergesort2(0, n-1);

	for (int i = 0; i<n; i++)
		printf("%d ", S[i]);
}

chogahui05 6년 전 0

일단 아래에서도 런타임이 뜨네요.

/*
14
4 7 8 2 3 4 1 4 2 3 4 2 3 1
*/

chogahui05 6년 전 1

qkr님 의도대로 머지를 수행하시려면..

int * U = (int *)malloc(sizeof(int)*(high - low + 1)*2);

를

int *U = (int *)malloc(sizeof(int)*배열 전체 사이즈);

로 바꾸셔야 겠죠. 그런데 이 경우는 공간 복잡도가 O(nlogn)쯤 됩니다.

int * U = (int *)malloc(sizeof(int)*(high - low + 1));

이 코드로 수행할 수 있는 방법이 있습니다. 이 경운 공간 복잡도가 O(n)이고요.

k값만 잘 변경하시면 런타임 안 뜹니다.

qkrguswndk 6년 전 0

감사합니다 해결되었습니다.

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

문제

문제

출처

ICPC

머지소트 런타임 에러

qkrguswndk 6년 전 0

chogahui05 6년 전 0

chogahui05 6년 전 1

qkrguswndk 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말