글 읽기 - C언어 시간초과 질문 있습니다.

joonbo97 3년 전 0

최소힙으로 맞게 구현한것같은데 자꾸 시간초과가 나는 이유를 모르겠습니다..

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

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

typedef struct _HEEP {  // size는 인덱스 값임!
	int size;
	int num[100001];
}heep;

int compare(int a, int b)
{
	if (a < b)
		return a;
	else
		return b;
}

heep insert(heep H, int N)
{
	H.size++;
	H.num[H.size] = N;
	int a = H.size;
	int b = a / 2;

	while (H.num[a] < H.num[b])
	{
		if (b == 0)
			break;
		swap(H.num, a, b);
		a = b;
		b = a / 2;
	}

	return H;
}

heep del(heep H)//H.num[1]을 반환하는 작업은 delete에서 하는 일이 아님!
{
	H.num[1] = H.num[H.size];//맨끝값을 맨위로 가져옴
	
	int a = 1;//b
	int b = 2 * a;
	int c = b + 1;
	H.size--;

	while (b <= H.size && c <= H.size)
	{
		if (H.num[b] < H.num[c])//a와 b를 비교해야함!
		{
			if (H.num[a] > H.num[b])
			{
				swap(H.num, a, b);
				a = b;
				b = 2 * a;
				c = b + 1;
			}
			else
				break;
		}
		else//a와 c를 비교해야함!
		{
			if (H.num[a] > H.num[c])
			{
				swap(H.num, a, c);
				a = b;
				b = 2 * a;
				c = b + 1;
			}
			else
				break;
		}
	}

	return H;
}

int main() {
	int N, temp;
	heep H;
	H.size = 0;
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &temp);

		if (temp == 0)
		{
			if (H.size == 0)
				printf("0\n");
			else
			{
				printf("%d\n", H.num[1]);
				H = del(H);
			}
		}
		else
		{
			H = insert(H, temp);
		}
	}
}

sonjaewon 3년 전 1

말해드리자면 heep 가 아니라 heap 입니다...

kth001 3년 전 0

여러 실험을 해본 결과 함수에서 리턴할때랑 함수에 값을 넘겨줄때 힙이 크기가 꽤 크다보니 시간이 오래걸리는것같습니다

힙을 전역변수로 선언하세요 그럼 틀렸습니다 라고 나올텐데 어디가 틀렸는지는 직접 찾아보시길

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

문제

문제

출처

ICPC

C언어 시간초과 질문 있습니다.

joonbo97 3년 전 0

sonjaewon 3년 전 1

kth001 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말