[백준] 28279 덱2 (C++)

https://www.acmicpc.net/problem/28279

28279번: 덱 2

 

 

 

 

 

 

 

#include<iostream>
using namespace std;

#define MAX 1000000

int deq[MAX * 2];
int head = MAX - 1;
int tail = MAX;
int vSize = 0;

int Empty()
{//6
	if ((tail - head - 1) == 0)
		return 1;
	else
		return 0;
}

void PushFront(int x)
{//1
	deq[head--] = x;
}

void PushBack(int x)
{//2
	deq[tail++] = x;
}

int PopFront()
{//3
	if (Empty())
		return -1;
	else
		return deq[++head];
}

int PopBack()
{//4
	if (Empty())
		return -1;
	else
		return deq[--tail];
}

int Count()
{//5
	return tail - head - 1;
}


int Front()
{//7
	if (Empty())
		return -1;
	else
		return deq[head + 1];
	
}

int Back()
{//8
	if (Empty())
		return -1;
	else
		return deq[tail - 1];
}


int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;

	int order;
	for (int i = 0; i < n; i++)
	{
		cin >> order;
        
		//////////////////출력
		switch (order)
		{
		case 1:
			{
			int x;
			cin >> x;
			PushFront(x);
			}
		break;

		case 2:
			{
			int x;
			cin >> x;
			PushBack(x);
			}
		break;

		case 3:
			cout << PopFront() << "\n";
		break;

		case 4:
			cout << PopBack() << "\n";
		break;

		case 5:
			cout << Count() << "\n";
		break;

		case 6:
			cout << Empty() << "\n";
		break;

		case 7:
			cout << Front() << "\n";
		break;

		case 8:
			cout << Back() << "\n";
		break;


		}
	}
}

 

 

처음에는 그냥 배열을 1000000개 잡아두고

Size = 0하나 잡아두고

PushFront, PopFront 할 때 마다 앞으로 다 땡기고,, 뒤로 다 밀고,,

이런 식으로 했었다

 

Size만 늘려주고 빼주고.. 변수 처리는 쉬웠지만 

역시나 배열 전체를 한칸씩 옮기는 작업은 시간이 많이 소요된다

 

그래서 배열을 그냥 맥시멈(1000000) * 2로 잡아주고

Front처리는 0~999999, Back처리는 1000000~1999999에서 하는걸로 했다

그리고 변수로 head 와 tail을 받아와서 현재 가장 앞쪽이 몇번인지는 head가 , 가장 뒤쪽이 몇번인지는 tail이 관리하도록 두었다

 

그러니 전체적인 식도 짧고 간단해지고 

배열안의 값을 옮길 필요도 없으니 시간도 당연히 빨라졌다