글 읽기 - 원형큐 시간 초과 문제입니다

mim501 2년 전 0

원형큐로 이 문제를 풀었는데 맨 처음에 큐 사이즈를 최대 n 갯수인 500000으로 잡았는데 계속 시간초과가 나와서

큐 사이즈를 500000의 4배인 2000000으로 설정했더니 정답이라고합니다. 왜 그런건가요??

선형큐가 아닌 원형큐인데 굳이 큐의 배열크기를 엄청 크게 잡을 필요가 있나여??

#include<stdio.h>
#include<stdlib.h>
#define MAX 500000  ///500000이 시간초과가 나오고 2000000이 정상 작동합니다. 이 부분이 궁금해요 ㅠㅠ
typedef struct queue {

	int front, rear;
	int data[MAX];
	
}queue;


void delete_queue(queue* q) {
	if (q->rear == q->front)
		return ;
	else
		q->front = (q->front + 1) % MAX;
}

int main(void) {

	int n;
	scanf("%d", &n);
	queue* q = (queue*)malloc(sizeof(queue));
	q->front = 0;
	q->rear = 0;
	for (int i = 1; i <= n; i++) {
		q->data[i] = i;
		q->rear++;
	}
	while ((q->front + 1) % MAX != q->rear) {
		
		delete_queue(q);
		if ((q->front + 1) % MAX == q->rear)
			break;
		
        q->data[((++q->rear) % MAX)] = q->data[++(q->front)];
			
    }
	
    printf("%d", q->data[q->rear]);
	return 0;

}

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

문제

문제

출처

ICPC

원형큐 시간 초과 문제입니다

mim501 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말