BOJ 5430 AC

이 문제를 읽어보면 배열을 뒤집고 삭제하는 작업이 여러번 반복되는 문제임을 알수 있다. 일반 백터를 활용하여 풀기를 시도한다면 원소의 제일 첫번째를 삭제하는것 뿐만아니라 값을 뒤집는것 또한 귀찮은 일이다. 이때 이를 손쉽게 할수 있는 덱(dequeue)을 사용하면 간단히 해결 가능하다.

 

입력 문자열을 파싱하여 R일경우 뒤집힘을 알수 있다. 여기서 덱의 특징을 이용한 간단한 트릭을 사용한다면 다음과 같이 생각해볼 수 있다. 

 

1. R이 나오지 않은 상태에서 D를 만난다면 덱의 front에서 pop을 해준다.

2. R이 나올때마다 pop의 위치를 바꿔준다.

 

위의 방법을 반복하여 수행한 후 마지막 출력시 현재 상태가 front인지 back 인지 확인 후 알맞게 출력해 주면된다.

 

#include<iostream>
#include<string>
#include<deque>
using namespace std;

void parse(deque<int> &dq, string arr)
{
	string s = "";
	for(int i = 0; i < arr.size(); i++)
	{
		if(arr[i] == ']' || arr[i] == '[' || arr[i] == ',')
		{
			if(!s.empty())
			{
				dq.push_back(stoi(s));
				s = "";
			}
		}
		else
		{
			s.push_back(arr[i]);
		}
	}
}

void solution()
{
	deque<int> dq;
	string p;
	int n;
	string arr;
	bool isFront = true;

	cin >> p >> n >> arr;

	parse(dq, arr);

	for(int i = 0; i < p.size(); i++)
	{
		if(p[i] == 'D')
		{
			if(dq.empty())
			{
				cout << "error\n";
				return;
			}
			else
			{
				if(isFront)
				{
					dq.pop_front();
				}
				else
				{
					dq.pop_back();
				}
			}
		}
		if(p[i] == 'R')
		{
			if(isFront)
			{
				isFront = false;
			}
			else
			{
				isFront = true;
			}
			
		}
	}

	if(dq.empty())
	{
		cout << "[]\n";
	}
	else
	{
		string result = "[";
		if(isFront)
		{
			while(!dq.empty())
			{
				result += to_string(dq.front()) + ",";
				dq.pop_front();
			}
			result[result.size()-1] = ']';
		}
		else
		{
			while(!dq.empty())
			{
				result += to_string(dq.back()) + ",";
				dq.pop_back();
			}
			result[result.size()-1] = ']';
		}

		cout << result<<"\n";
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int t;
	cin >> t;

	for(int i = 0; i < t; i++)
	{
		solution();
	}

}