글 읽기 - merge sort

tosk3927 5년 전 0

자꾸 틀렸다는데 뭐가 잘못된 건지 모르겠네요ㅠㅠ 테스트케이스를 여러개 돌려봐도 원인을 모르겠습니다.ㅠㅠ

int 면 overflow가 난다길래 아래는 long으로 고쳤습니다..ㅠ

한번만 봐주세요ㅠㅠ

using namespace std;

long int *arr;
long int *sorted_arr;


void mergeSort( long int left, long int right);
void merge(long int left,long  int mid, long int right);

int main(){

	long int size = 0; 
	cin >> size;

	arr = new long int[size];
	sorted_arr = new  long int[size];

	for(long int i =0 ;i < size; i++){ // input data
		cin >> arr[i];
	} 

	//mergesort
	mergeSort(0, size-1);

	for(long int i = 0 ;i < size; i++){ // output data
		cout << sorted_arr[i] << "\n";
	} 


	delete [] arr;
	delete [] sorted_arr;

	return 0;

}

void merge(long  int left, long int mid ,long  int right){
	long  int l1,l2, i;

	//merge
	for(l1 = left, l2 = mid + 1, i = left; l1 <= mid && l2 <= right; i++ ){
		if(arr[l1] <= arr[l2])
			sorted_arr[i] = arr[l1++];
		else
			sorted_arr[i] = arr[l2++];
	}

	while(l1 <= mid)    
       sorted_arr[i++] = arr[l1++];

    while(l2 <= right)   
       sorted_arr[i++] = arr[l2++];

    for(i = left; i <= right; i++) //update merged arr 
        arr[i] = sorted_arr[i];

}

void mergeSort(long int left,  long int right){

	long int mid;
	if(left < right){
		mid = (left + right)/2;
		mergeSort(left,mid);
		mergeSort(mid+1, right);
		merge(left,mid,right);
			
	}
}

kimsy96 5년 전 0

문제에서 입력되는 수의 제한이 절대값 1 ,000,000 이하라

그냥 int형으로 입력받아서 정렬하면 되는 문제입니다

굳이 long long형을 쓸필요는없어보입니다

jh05013 5년 전 0

1
1

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

문제

문제

출처

ICPC

merge sort

tosk3927 5년 전 0

kimsy96 5년 전 0

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말