글 읽기 - 시간초과가 납니다.

seonjoo2030 5년 전 0

코드 수정해서 다시 해도 시간 초과 납니다....ㅜㅜ

#include <stdio.h>

void array_swap(int* arr, int a, int b)
{
	int temp;
	temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

void Heapifiy(int* arr, int parent_position, int heap_size)
{
	int left, right, largest;
	left = 2 * parent_position + 1;
	right = 2 * parent_position + 2;

	largest = parent_position;
	if ((left < heap_size) && (arr[left] > arr[largest]))
		largest = left;

	else
		largest = parent_position;

	if ((right < heap_size) && (arr[right] > arr[largest]))
		largest = right;



	if (largest != parent_position)
	{
		array_swap(arr, parent_position, largest);
		Heapifiy(arr, largest, heap_size);
	}

}

void Build_heap(int* arr, int length)
{
	int parent_position;

	for (parent_position = (length / 2) - 1; parent_position >= 0; parent_position--)
	{
		Heapifiy(arr, parent_position, length);
	}
}

void heapSort(int* arr, int heap_size)
{
	for (int i = heap_size - 1; i > 0; i--)
	{
		int tmp = arr[0];
		arr[0] = arr[i];
		arr[i] = tmp;
		heap_size = heap_size - 1;
		Build_heap(arr, heap_size);
	}
}

int arr[1000001];
int main()
{

	int input;
	scanf("%d", &input);

	for (int i = 0; i < input; i++)
	{
		scanf("%d", &arr[i]);
	}

	Build_heap(arr, input);
	heapSort(arr, input);
	for (int i = 0; i < input; i++)
	{
		printf("%d\n", arr[i]);
	}
}

djm03178 5년 전 0

left나 right가 heap_size 이상이 되면 arr[left], arr[right]에 단 한 번이라도 접근해서는 안 되는데, 17번째 줄에서 비교를 위해 먼저 접근하고 있습니다.

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

문제

문제

출처

ICPC

시간초과가 납니다.

seonjoo2030 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말