글 읽기 - merge sort로 짰는데 자꾸 시간초과가 뜹니다 왜일까요?

dmswn0261 3년 전 0

자꾸만 시간초과가 떠요 아무리 봐도 mergesort랑 다를게 없어보이고, 예제 문제도 맞는 결과로 나오는데 왜그럴까요?ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

int arr[10000][2] = { 0, };
int ar[10000][2];
int count;
void mergesort(int s1, int e1, int e2) {
	int i, j, save;

	i = s1;
	j = e1 + 1;
	save = s1;
	while (i<=e1&&j<=e2) {
		if (arr[i][0] < arr[j][0]) {
			ar[s1][0] = arr[i][0];
			ar[s1++][1] = arr[i++][1];
		}
		else if (arr[i][0] > arr[j][0]) {
			ar[s1][0] = arr[j][0];
			ar[s1++][1] = arr[j++][1];
		}
		else {
			if (arr[i][1] > arr[j][1]) {
				ar[s1][0] = arr[j][0];
				ar[s1++][1] = arr[j++][1];
			}
			else {
				ar[s1][0] = arr[i][0];
				ar[s1++][1] = arr[i++][1];
			}
		}
	}

	if (i <= e1) {
		while(i<=e1) {
			ar[s1][0] = arr[i][0];
			ar[s1++][1] = arr[i][1];
		}
	}
	else {
		while(j<=e2){
			ar[s1][0] = arr[j][0];
			ar[s1++][1] = arr[j][1];	
		}
	}
	for (int k = save; k <= e2; k++) {
		arr[k][0] = ar[k][0];
		arr[k][1] = ar[k][1];
	}

}

void merge(int start, int end) {
	int mid;
	if (start < end) {
		mid = (start + end) / 2;
		merge(start, mid);
		merge(mid+ 1, end);
		mergesort(start, mid, end);
	}
}
int main() {

	scanf("%d", &count);

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

Green55 3년 전 2

i와 e1 모두 값이 바뀌지 않는데 이 while문을 탈출 할 수 있나요?

while(i<=e1) {
    ar[s1][0] = arr[i][0];
    ar[s1++][1] = arr[i][1];
}

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

문제

문제

출처

ICPC

merge sort로 짰는데 자꾸 시간초과가 뜹니다 왜일까요?

dmswn0261 3년 전 0

Green55 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말