글 읽기 - [c] 어떻게하면 시간초과를 없앨 수 있을까요?

mun9769 3년 전 0

queue이긴 하지만 따지고보면 queue 구조체에 배열이 있는 구조입니다

dequeue함수를 보면 O(n)으로 시간이 오래 걸리는듯 싶습니다.

배열이 아닌 Node struct를 만들면 더 빠를까요?

#include <cstdio>
#include <cstdlib>
using namespace std;

typedef struct {
	int max;
	int num;
	int *que;
} ArrayIntQueue;

int Create(ArrayIntQueue *a, int _max)
{
	a->num = 0;
	a->que = (int*)calloc(_max, sizeof(int));
	a->max = _max;
	if(a->que == NULL) return -1;
}

void Enqueue(ArrayIntQueue *a, int x)
{
	if(a->num >= a->max) return -1;
	a->que[a->num++] = x;

}

int Dequeue(ArrayIntQueue *a)
{
	if(a->num <= 0) return -1;
	a->num--;
	int res = a->que[0];
	int i;
	for(i=0; i<a->num; i++)
		a->que[i] = a->que[i+1];
	return res;
}

int main()
{
	int n;
	scanf("%d",&n);

	ArrayIntQueue a;
	Create(&a, n);
	for(int i=1; i<=n; i++)
		Enqueue(&a, i);
	while(a.num>1)
	{
		Dequeue(&a);
		if(a.num<=1) break;
		Enqueue(&a, Dequeue(&a));
	}
	printf("%d",a.que[0]);


	return 0;
}

nahwasa 3년 전 0

넹 dequeue 때문입니다.

뭐 이 구조에서 크게 바꾸지 않고 한다면,

빼는건 낮은 인덱스부터, 넣는건 높은 인덱스쪽에.. 이런 개념으로 하신다면

구조체에 s,e 정도 두시고(처음엔 둘다 0) 대강 아래와 같이 하시면 되지 않나 싶습니다. (대강한거라 다듬으셔야겟으나, 뭘 말하려는진 아실꺼라 생각합니다.)

void Enqueue(ArrayIntQueue *a, int x)
{
	if(a->e >= a->max) return -1;
	a->que[a->e++] = x;

}

int Dequeue(ArrayIntQueue *a)
{
	if(a->s > a->e) return -1;
	return a->que[a->s++];
}

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

문제

문제

출처

ICPC

[c] 어떻게하면 시간초과를 없앨 수 있을까요?

mun9769 3년 전 0

nahwasa 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말