[Baekjoon] 10866번: 덱

 

 

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

10866번: 덱

 

---

 

문제 해결 과정

착안

덱(deque) 자료 구조는 double-ended queue를 의미하며, 양방향에서 데이터의 삽입 및 출력이 가능한 큐 자료 구조이다. 큐를 구현할 때와 마찬가지로 데이터의 입출력 과정에서 Front와 Rear 변수를 제어함으로써 덱 자료 구조를 표현하고자 하였다.

 

편의상 배열 형태로 구현하고자 하였고, Front, Rear 변수를 각각 현재 존재하는 데이터의 가장 앞, 뒤 요소의 인덱스를 나타내도록 사용하였다. 양방향에서 데이터의 삽입과 출력이 가능한 점을 고려해 문제의 요구 수준을 만족하는 충분히 큰 배열을 선언한 다음 배열의 가운데 인덱스부터 시작할 수 있도록 Front, Rear 변수를 초기화하고자 하였다. 이때 덱이 비어있는 상태는 Rear의 값이 Front보다 작은 상태로 표현하고자 하였다.

 

양방향으로 확장이 되는 형태이므로, 데이터의 입출력에 따라 다음과 같이 작동하도록 구상하였다.

 

• push_front(): Front의 값을 감소한 뒤 데이터를 Front의 위치에 삽입
• push_back(): Rear의 값을 증가한 뒤 데이터를 Rear의 위치에 삽입
• pop_front(): 현재 Front 위치에 존재하는 데이터를 출력한 뒤 Front의 값을 증가
• pop_back(): 현재 Rear 위치에 존재하는 데이터를 출력한 뒤 Rear의 값을 감소

 

pop_front(), pop_back()을 통해 실제로 Front 또는 Rear 위치에 있는 요소를 배열에서 삭제할 필요까지는 없기 때문에, 단순히 출력만 수행한 뒤 Front, Rear의 값을 제어하여 pop을 수행한 값에는 접근할 수만 없도록 구현하고자 하였다.

 

구현

앞에서 구상한 것과 같이 프로그래밍하였는데, 문제에서 요구하는 것과 같이 동작을 수행했을 때 인덱스가 배열 범위를 초과하지 않도록 배열 크기를 선언하고 Front 및 Rear 변수를 제어하는 데에 중점을 두어 구현하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int Deque[19998];
int Front = 10000;
int Rear = Front - 1;
int Size;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N;
	cin >> N;

	while (N--)
	{
		string Op;
		cin >> Op;

		if (Op == "push_front")
		{
			cin >> Deque[--Front];
			Size++;
		}
		else if (Op == "push_back")
		{
			cin >> Deque[++Rear];
			Size++;
		}

		else if (Op == "pop_front")
		{
			if (Rear < Front)
				cout << "-1\n";
			else
			{
				cout << Deque[Front++] << "\n";
				Size--;
			}
		}
		else if (Op == "pop_back")
		{
			if (Rear < Front)
				cout << "-1\n";
			else
			{
				cout << Deque[Rear--] << "\n";
				Size--;
			}
		}

		else if (Op == "size")
			cout << Size << "\n";
		else if (Op == "empty")
			cout << (Rear < Front) << "\n";

		else if (Op == "front")
		{
			if (Rear < Front)
				cout << "-1\n";
			else
				cout << Deque[Front] << "\n";
		}
		else if (Op == "back")
		{
			if (Rear < Front)
				cout << "-1\n";
			else
				cout << Deque[Rear] << "\n";
		}
	}

	return 0;
}

 

실행 결과