글 읽기 - 이 문제 O(n)은 통과가 안되는 건가요?

pok35 1년 전 0

연결리스트로 접근을했는데 시간초과가 자꾸 나네요.. 나와 있는 테스트케이스는 다 넣은 것 같습니다

#include<stdio.h>
#include<stdlib.h>

struct node {
	int data;
	struct node* next_node;
	struct node* prev_node;

};

struct queue {
	int queue_lenth;
	struct node* tail;
	struct node* head;

};

void make_double_queue(queue* queue_info, int input) {

	node* new_node = (node*)malloc(sizeof(node));

	node* cursor = queue_info->head;
	//////////////////////////////////////////////////
	if (new_node) {
		new_node->data = input;
		new_node->next_node = NULL;
		new_node->prev_node = NULL;
	}

	////////////////////////////////////////////////////////////
	if (queue_info->queue_lenth == 0) {
		queue_info->head = new_node;
		queue_info->tail = new_node;

	}
	else { 

		int shift_num = 0;

		while (cursor->data > input) {

			if (cursor->next_node == NULL) {
				shift_num++;
				break;
			}
			cursor = cursor->next_node;
			shift_num++;

		}

		if (shift_num == 0) {
			cursor->prev_node = new_node;
			new_node->next_node = cursor;

			queue_info->head = new_node;
		}
		else if (shift_num == queue_info->queue_lenth) {
			cursor->next_node = new_node;
			new_node->prev_node = cursor;

			queue_info->tail = new_node;
		}
		else {
			new_node->prev_node = cursor->prev_node;
			new_node->next_node = cursor;

			cursor->prev_node = new_node;
			cursor->prev_node->prev_node->next_node = new_node;

		}

	}
	queue_info->queue_lenth += 1;
}

void pop_max(queue * queue_info) {

	if (queue_info->head == NULL) return;
	node * temp_head_point = queue_info->head;

	queue_info->head = queue_info->head->next_node;
	queue_info->queue_lenth -= 1;

	if (queue_info->queue_lenth == 0) {
		queue_info->tail = NULL;
	}

	if (queue_info->head != NULL) {
		queue_info->head->prev_node = NULL;
	}



}

void pop_min(queue* queue_info) {

	if (queue_info->tail == NULL) return;

	node* temp_tail_point = queue_info->tail;

	queue_info->tail = queue_info->tail->prev_node;
	queue_info->queue_lenth -= 1;

	if (queue_info->queue_lenth == 0) {
		queue_info->head = NULL;
	}

	if (queue_info->tail != NULL) {
		queue_info->tail->next_node = NULL;
	}


}

int main(void) {

	freopen("텍스트.txt", "r", stdin);
	
	int t_case;
	scanf("%d", &t_case);

	for (int T = 0; T < t_case; T++) {
		queue* queue_info = (queue*)malloc(sizeof(queue)); // queue_info

		if (queue_info) {

			queue_info->queue_lenth = 0;
			queue_info->tail = NULL;
			queue_info->head = NULL;
		}

		int command_num;

		scanf("%d", &command_num);

		for (int now_command = 0; now_command < command_num; now_command++) {

			char command;
			int input;

			scanf("\n%c", &command);
			scanf("%d", &input);

			if (command == 'I') {
				make_double_queue(queue_info, input);
			}
			else if (command == 'D') {
				if (input == 1) {
					pop_max(queue_info);
				}
				else if (input == -1) {
					pop_min(queue_info);
				}
			}

		}

		if (queue_info->queue_lenth == 0) {
			printf("EMPTY\n");
		}
		else {
			printf("%d %d\n", queue_info->head->data, queue_info->tail->data);
		}
		


	}

	return 0;
}

amsminn 1년 전 2

O(n)이 아니라 O(qn) 같습니다.

pok35 1년 전 0

맞네요 감사합니다!!

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

문제

문제

출처

ICPC

이 문제 O(n)은 통과가 안되는 건가요?

pok35 1년 전 0

amsminn 1년 전 2

pok35 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말