stella6767 3년 전 0

수 정렬하기 2 합병정렬로 오름차순 정렬해봤는데 백준 저지에서는 런타임 에러가 뜨네요. 혹시 원인을 알 수 있을까요?

#include <iostream>

using namespace std;

void merge(int list[], int low, int mid, int high) {
	int n1 = low, n2 = mid + 1, s = low, sorted[1000] = { 0 }, i;
	 while (n1 <= mid && n2 <= high) {
		 if (list[n1] <= list[n2]) sorted[s++] = list[n1++];
		 else sorted[s++] = list[n2++];
		
	}
	 if (n1>mid) {
		 while (n2 <= high)
			 sorted[s++] = list[n2++];
	 }
	 else while (n1 <= mid) sorted[s++] = list[n1++];
	 for (i = low; i <= high; i++) list[i] = sorted[i];
	
}
void merge_sort_DC(int list[], int low, int high) {
	int middle;
	 if (low <high) {
		 middle = (low + high) / 2;
		 merge_sort_DC(list, low, middle);
		 merge_sort_DC(list, middle + 1, high);
		 merge(list, low, middle, high);
		
	}
	
}


int main() {

	int* data;
	int n;

	int low, high;

	cin >> n;
	data = new int[n];

	for (int i = 0; i < n; i++)
	{
		cin >> data[i];
	}


	low = 0;
	high = n-1;

	merge_sort_DC(data, low, high);

	for (int i = 0; i < n; i++)
	{
		cout << data[i] << "\n";
	}


}

seico75 3년 전 1

merge 함수에서 중간 배열 sorted 크기가 1000 밖에 안되네요.

stella6767 3년 전 0

죄송하지만 좀 더 정확한 이유를 여쭤볼 수 있을까요..?

seico75 3년 전 0

문제에서 N은 1'000'000 이 최대이니 merge_sort_DC안에서 둘로 나눠서 500'000 두개를 소팅하고 merge 할텐데..

merge 내에서는 500'000 두개를 합치려면 2*1'000'000 크기의 배열이 필요합니다.

그런데 1'000만 잡았고 그 배열을 써서 1'000'000 배열을 머지하려니 잘못된 주소에 접근해서 죽게 됩니다.

stella6767 3년 전 0

..늦었지만 감사합니다!!

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

문제

문제

출처

ICPC

혹시 왜 런타임 에러가 나는지 알수 있을까요.

stella6767 3년 전 0

수 정렬하기 2 합병정렬로 오름차순 정렬해봤는데 백준 저지에서는 런타임 에러가 뜨네요. 혹시 원인을 알 수 있을까요?

seico75 3년 전 1

stella6767 3년 전 0

seico75 3년 전 0

stella6767 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말