(C++) [백준 10866번] 덱

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

10866번: 덱

 

예전에 썼던 덱 문제의 설명이 완전히 이상한 것 같아서, 지금도 부족하긴 하지만 다시 설명해보고자 글을 쓴다.

 

이 문제 같은 경우 총 8개의 연산을 구현해야 한다.

 

• push_front X: 정수 X를 덱의 앞에 넣는다.
• push_back X: 정수 X를 덱의 뒤에 넣는다.
• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 덱에 들어있는 정수의 개수를 출력한다.
• empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
• front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

 

초기에 풀었을 때는 head/tail의 인덱스를 0으로 두었는데 바킹독님 강의를 들어 보니 덱은 양쪽으로 확장시키는게 편하다 보니 head/tail의 인덱스를 중간에 두는게 더 낫다는걸 알게 되었다.

#define MAX 1000005
int dat[2 * MAX + 1];
int tail = MAX, head = MAX;

따라서 나같은 경우에는 배열의 인덱스를 2*MAX+1, tail,head를 그 중간 지점으로 초기화해주었다.

head가 배열의 앞부분으로 가고, tail가 배열의 뒷부분으로 간다고 생각하면 편하다.

 

1)push_front:

void push_front(int x)
{
	dat[--head] = x;
}

나같은 경우 front를 전위연산자로 두었다. head와 tail을 둘 다 후위연산자로 두면 front와 back을 1회씩 수행했을 때 같은 인덱스에 위치할 수 있기 때문이다.

2)push_back:

void push_back(int x)
{
	dat[tail++] = x;
}

따라서 back은 후위연산자로 두었다.

push같은 경우 단순히 1씩 감소하거나 증가시키면 되므로 별로 어려울게 없다.

 

3)pop_front:

int pop_front()
{
	if (empty()) return -1;
	int t = dat[head++];
	return t;
}

덱이 비어있다면 -1을 출력해야 하므로 만약 비어있다면 -1을 리턴하고, 아니라면 dat[head++]를 리턴해주면 된다.

head++을 하면서 head의 인덱스가 1 증가되므로 pop한 효과가 있고, 현재 아까 front에서 전위연산자를 이용했기 때문에 head가 가리키는 원소가 front이기 때문에 후위연산자를 이용해야 한다.

이후 저장된 t를 리턴하면 된다.

 

4)pop_back:

int pop_back()
{
	if (empty()) return -1;
	int t = dat[--tail];
	return t;
}

pop_front와 마찬가지지만 push_back때 후위연산자를 이용했기 때문에 tail이 가리키는 곳에는 원소가 없고, tail-1이 가리키는 곳에 원소가 있기 때문에 전위연산자를 이용해서 t에 값을 저장하고 리턴해주면 된다.

 

5)front:

int front()
{
	if (!empty())
		if (dat[head] == 0)
			return back();
		else 
		return dat[head];
	else return -1;
}

내가 가장 어려워했던 부분인데, 먼저 덱이 비어있는 경우를 체크하기 위한 if문이 있고, 덱이 비어있지 않다면

덱의 head부분에 원소가 없는지도 체크해야 하기 때문에 if문이 하나 더있다. 만약 head부분에 원소가 없다면 push_front를 이용해서 원소가 들어오지 않았으므로 back()을 호출하고, 아니라면 head가 가리키는 인덱스의 원소를 호출하면 된다.

만약 덱이 비어있다면 -1을 리턴하면 된다.

 

6)back:

int back()
{
	if (!empty())
		if (dat[tail-1] == 0)
			return front();
	else return dat[tail - 1];
		else return -1;
}

front와 거의 같은데 아까 push_back에서 후위연산자를 이용했으므로 tail-1이 가리키는 곳에 원소가 있다는 것만 조심하면 된다.

 

7)size:

int size()
{
	return tail - head;
}

단순히 tail - head를 하면 된다.

 

8)empty:

int empty()
{
	if (head == tail) return 1;
	else return 0;
}

단순히 head와 tail이 같다면(원형 덱이 아니므로) 원소가 없는 상태이므로 1을 리턴하고, 아니라면 0을 리턴하면 된다.

 

 

[예제 1 출력 결과]

아래는 전체 코드이다.

#include <iostream>
using namespace std;
#define MAX 1000005
int dat[2 * MAX + 1];
int tail = MAX, head = MAX;
int back();
int empty()
{
	if (head == tail) return 1;
	else return 0;
}
void push_front(int x)
{
	dat[--head] = x;
}
void push_back(int x)
{
	dat[tail++] = x;
}
int pop_front()
{
	if (empty()) return -1;
	int t = dat[head++];
	return t;
}
int pop_back()
{
	if (empty()) return -1;
	int t = dat[--tail];
	return t;
}
int front()
{
	if (!empty())
		if (dat[head] == 0)
			return back();
		else 
		return dat[head];
	else return -1;
}
int back()
{
	if (!empty())
		if (dat[tail-1] == 0)
			return front();
	else return dat[tail - 1];
		else return -1;
}
int size()
{
	return tail - head;
}
int main(){
int t, c;
string s;
cin >> t;
for (int i = 0; i < t; i++)
{
	cin >> s;
	if (s == "push_front")
	{
		cin >> c;
		 push_front(c);
	}

	else if (s == "push_back")
	{
		cin >> c;
		 push_back(c);
	}
	else if (s == "pop_front")
		cout <<  pop_front() << "\n";
	else if (s == "pop_back")
		cout <<  pop_back() << "\n";
	else if (s == "size")
		cout <<  size() << "\n";
	else if (s == "empty")
		cout <<  empty() << "\n";
	else if (s == "front")
		cout <<  front() << "\n";
	else if (s == "back")
		cout <<  back() << "\n";

}
}