글 읽기 - c 합병정렬 시간초과가 납니다 ㅠㅠ

ahj1077 3년 전 0

합병정렬구현해 봤는데 시간초과가 나더군요 ㅠㅠ 입출력에서 시간을 줄이는건 다 한거 같은데 뭐가 문제일까요?? ㅠㅠ

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

#define MAX 1000000

int arr[MAX];
int temp[MAX];

void merge(int start, int end) {
	if (start == end) {
		return;
	}

	merge(start, (start+end)/2);
	merge((start+end)/2+1, end);

	int left1 = start;
	int left2 = (start + end)/ 2+1;
	int i;

	for (i = 0; i < end - start+1; i++) {
		temp[start + i] = arr[start + i];    //temp배열에 복사
	}

	i = start;

	while(left1 < left2 && left2 <= end) {
		if (temp[left1] > temp[left2]) {
			arr[i++] = temp[left2++];

			if (left2 > end) {
				memcpy(&arr[i],&temp[left1],sizeof(int)*(left2-left1-1));
				break;
			}			
		}
		else if (temp[left1] < temp[left2]) {
			arr[i++] = temp[left1++];

			if (left1 >= left2) {
				memcpy(&arr[i], &temp[left2], sizeof(int)*(end - left2));
				break;
			}
		}
	}
}

int main() {
	int n,i;
	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		scanf("%d",&arr[i]);
	}
	merge(0, n-1);
	
	for (i = 0; i < n; i++) {
		printf("%d\n",arr[i]);
	}
	return 0;
}

djm03178 3년 전 0

시간 초과가 나는 이유는 temp[left1] == temp[left2]일 때 아무것도 안 하기 때문입니다.

이걸 고쳐도 틀리니, 원인을 찾아보세요.

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

문제

문제

출처

ICPC

c 합병정렬 시간초과가 납니다 ㅠㅠ

ahj1077 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말