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

qsccsq22 2년 전 0

아래 코드 중 어떤 부분 때문에 시간 초과가 뜰까요? ㅜㅜ

#include <iostream>
#include <stdlib.h>
using namespace std;
typedef struct Deque
{
	int num;
	struct Deque* prev;
	struct Deque* next;
}Node;

typedef struct
{
	Node* head;
	Node* tail;
}DQ;

void init_Deque(DQ* dq)
{
	dq->head = NULL;
	dq->tail = NULL;
}

int empty(DQ* dq)
{
	if (dq->head == NULL)
		return 1;
	else
		return 0;
}

void push_front(DQ* dq, int n)
{
	Node* temp = (Node*)malloc(sizeof(Node));
	temp->num = n;
	temp->prev = NULL;
	temp->next = NULL;
	if (dq->head == NULL)
	{
		dq->tail = temp;
	}
	else
	{
		temp->next = dq->head;
		(dq->head)->prev = temp;
	}
	dq->head = temp;
}

void push_back(DQ* dq, int n)
{
	Node* temp = (Node*)malloc(sizeof(Node));
	temp->num = n;
	temp->prev = NULL;
	temp->next = NULL;
	if (dq->tail == NULL)
	{
		dq->head = temp;
	}
	else
	{
		temp->prev = dq->tail;
		(dq->tail)->next = temp;
	}
	dq->tail = temp;
}

int pop_front(DQ* dq)
{
	int num;
	if (!empty(dq))
	{
		Node* temp = dq->head;
		num = temp->num;
		if (dq->head == dq->tail)
		{
			dq->head = NULL;
			dq->tail = NULL;
		}
		else
		{
			dq->head = (dq->head)->next;
		}
		free(temp);
		return num;
	}
	else
		return -1;
}

int pop_back(DQ* dq)
{
	int num;
	if (!empty(dq))
	{
		Node* temp = dq->tail;
		num = temp->num;
		if (dq->head == dq->tail)
		{
			
			dq->head = NULL;
			dq->tail = NULL;
		}
		else
		{
			dq->tail = (dq->tail)->prev;
		}
		free(temp);
		return num;
	}
	else
		return -1;
}

int size(DQ* dq)
{
	int cnt;
	Node* temp = dq->head;
	for (cnt = 0; temp; temp = temp->next)
		cnt++;
	return cnt;
}


int front(DQ* dq)
{
	if (!empty(dq))
		return (dq->head)->num;
	else
		return -1;
}

int back(DQ* dq)
{
	if (!empty(dq))
		return (dq->tail)->num;
	else
		return -1;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	DQ dq;
	int N, n;
	string x;
	init_Deque(&dq);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> x;
		if (x == "push_front")
		{
			cin >> n;
			push_front(&dq, n);
		}
		else if (x == "push_back")
		{
			cin >> n;
			push_back(&dq, n);
		}
		else if (x == "pop_front")
			cout << pop_front(&dq) << '\n';
		else if (x == "pop_back")
			cout << pop_back(&dq) << '\n';
		else if (x == "size")
			cout << size(&dq) << '\n';
		else if (x == "empty")
			cout << empty(&dq) << '\n';
		else if (x == "front")
			cout << front(&dq) << '\n';
		else
			cout << back(&dq) << '\n';
	}
	return 0;
}

qsccsq22 2년 전 0

이 코드를 단방향 링크드 리스트로 변환하면 성공이라고 뜹니다.

단방향 링크드 리스트랑 양방향 링크드 리스트랑 시간 복잡도가 많이 차이 나나요?

djm03178 2년 전 0

양방향과 단방향의 문제가 아닌, size를 구하기 위해 매번 루프를 돌리는 것과 push / pop을 할 때 하나씩 증가 / 감소시켜주면서 관리하는 것의 차이입니다.

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

문제

문제

출처

ICPC

시간 초과가 뜹니다.

qsccsq22 2년 전 0

qsccsq22 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말