글 읽기 - [c++] 병합정렬을 사용했는데도 시간초과가 떠요

kdjsfhef 2년 전 0

제가 생각할 수 있는데까지 줄였는데도 계속 시간초과가 뜨는데

이유를 모르겠습니다

#include <iostream>

using namespace std;

int x[100000];
int y[100000];
int sort_x[100000];
int sort_y[100000];
int n;

void merge(int m, int mid, int n) {
	int i = m;
	int j = mid + 1;
	int k = m;

	while (i <= mid && j <= n) {
		if (x[i] > x[j]) {
			sort_x[k] = x[j];
			sort_y[k] = y[j];
			j++;
		}

		else if (x[i] < x[j]) {
			sort_x[k] = x[i];
			sort_y[k] = y[i];
			i++;
		}

		else {
			if (y[i] > y[j]) {
				sort_x[k] = x[j];
				sort_y[k] = y[j];
				j++;
			}

			else {
				sort_x[k] = x[i];
				sort_y[k] = y[i];
				i++;
			}
		}
		k++;
	}

	if (i > mid) {
		for (int t = j; t <= n; t++) {
			sort_x[k] = x[t];
			sort_y[k] = y[t];
			k++;
		}
	}
	else {
		for (int t = i; t <= mid; t++) {
			sort_x[k] = x[t];
			sort_y[k] = y[t];
			k++;
		}
	}

	for (int t = 0; t <= n; t++) {
		x[t] = sort_x[t];
		y[t] = sort_y[t];
	}
}

void mergeSort(int m, int n) {
	if (m < n) {
		int mid = (m + n) / 2;

		mergeSort(m, mid);
		mergeSort(mid + 1, n);

		merge(m, mid, n);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	cin >> n;

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

	mergeSort(0, n - 1);

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

	return 0;
}

dldyddlwl 2년 전 0

// 자, merge 과정 맨 아래에 있는 for 루프입니다.

for (int t = 0; t <= n; t++) {            // n까지 하는 것은 아주 좋습니다!
		x[t] = sort_x[t];            // 그런데 0부터 시작하는 것이 과연 옳은가요?!! 다시 생각해봅시다
		y[t] = sort_y[t];
	}

kdjsfhef 2년 전 0

굳이 넣지 않아도 되는 값들을 넣고 있어서 시간초과가 뜨던것이군요

감사합니다!

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

문제

문제

출처

ICPC

[c++] 병합정렬을 사용했는데도 시간초과가 떠요

kdjsfhef 2년 전 0

dldyddlwl 2년 전 0

kdjsfhef 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말