글 읽기 - 병합 정렬을 공부하고 제출 했음에도 시간 초과가 났습니다.

kemin1910 1년 전 0

한 5번 정도 시간 초과를 내고 결국 구글링을 해서 병합 정렬에 대해 공부하고 손으로 직접 디버깅도 해보고 끝끝내 다른 사람의 코드도 봤지만 또 시간 초과가 났습니다. 이 문제는 어느 부분을 신경 써주어야 하는 문제이며 어떤 방식으로 접근해야 하는지 알 수 있을까요?

#include <iostream>
using namespace std;

void merge(int* arr, int* sortArr, int begin, int middle, int end) {
	int sortedIdx = begin;
	int i = begin;
	int j = middle + 1;

	while (i <= middle && j <= end) {
		if (arr[i] < arr[j])
			sortArr[sortedIdx] = arr[i++];
		else
			sortArr[sortedIdx] = arr[j++];

		sortedIdx++;
	}

	if (i > middle) {
		while (j <= end) {
			sortArr[sortedIdx++] = arr[j++];
		}
	}

	if (j > end) {
		while (i <= middle) {
			sortArr[sortedIdx++] = arr[i++];
		}
	}

	for (int k = begin; k <= end; k++) {
		arr[k] = sortArr[k];
	}
}

void mergeSort(int* arr, int* sortArr, int begin, int end) {
	if (begin < end) {
		int middle = (begin + end) / 2;
		mergeSort(arr, sortArr, begin, middle);
		mergeSort(arr, sortArr, middle + 1, end);
		merge(arr, sortArr, begin, middle, end);
	}
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	int* arr = new int[n];

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

	int* sortArr = new int[n];

	mergeSort(arr, sortArr, 0, n - 1);

	for (int i = 0; i < n; i++) {
		cout << arr[i] << endl;
	}

	return 0;
}

pill27211 1년 전 2

로직은 문제가 없는데 다만 출력 쪽에서.. endl 이 친구가 문제 입니다.

endl은 개행도 해주지만 이외에 버퍼 flush연산도 같이 수행하는데 이는 빠른 연산도 아닐 뿐더러 수십 만 번씩 누적 되다보면 결국 출력 하다가 TLE를 얻어맞게 됩니다.

물론 endl 자체가 문제가 아니라, 출력양이 많은 문제에서 사용은 적절치 않다는 것이죠.

따라서 단순 개행이 목적이라면 그냥 개행 문자('\n')를 출력해 주시는 게 좋습니다.

(참고)

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

문제

문제

출처

ICPC

병합 정렬을 공부하고 제출 했음에도 시간 초과가 났습니다.

kemin1910 1년 전 0

pill27211 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말