글 읽기 - 도와주세요~

josy1002 1년 전 0

병합 정렬로 풀었는데 시간 초과가 나네요 ㅠ 어떻게 하는 것이 좋을까요?

#include<iostream>

int temp[1000001];

using namespace std;

void sort(int arr[], int left, int mid, int right)
{
	int i, j, m;
 
	i = left;
	j = left;
	m = mid + 1;

	while (i <= mid && m <= right)
	{
		if (arr[i] > arr[m])
		{
			temp[j++] = arr[m++];
		}
		else
		{
			temp[j++] = arr[i++];
		}
	}

	if (i > mid)
	{
		for (int x = m; x <= right; x++)
		{
			temp[j++] = arr[x];
		}
	}
	else
	{
		for (int x = i; x <= mid; x++)
		{
			temp[j++] = arr[x];
		}
	}

	for (int y = left; y <= right; y++)
	{
		arr[y] = temp[y];
	}
}

void merge_sort(int arr[], int left, int right)
{
	int mid = (left + right) / 2;

	if (left < right)
	{
		merge_sort(arr, left, mid);
		merge_sort(arr, mid + 1, right);
		sort(arr, left, mid, right);
	}
}

int main()
{
	int N;

	cin >> N;

	int* arr = new int[N];

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

	merge_sort(arr, 0, N - 1);


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

	return 0;
}

adung7 1년 전 1

우선 66번째줄에 동적할당을 하셨으므로 메인함수 종료되기 전에 delete[] 연산을 해주시고

78번째 줄에서 endl을 쓰셨는데 기본적으로 endl은 개행하는것외의 하는것이 또 있어서 연산이 매우 느립니다

따라서 endl을 '\n' 단순한 개행으로 바꿔주시면 정답이 되고 ios::sync_with_stdio(false); cin.tie(nullptr); 메인함수 시작되고 나서 이 구문 추가해주시면 입출력 속도가 빨라집니다.

josy1002 1년 전 0

감사합니다!

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

문제

문제

출처

ICPC

도와주세요~

josy1002 1년 전 0

adung7 1년 전 1

josy1002 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말