백준 18115번: 카드 놓기

 

풀이

  기술 3가지를 보면 카드 더미의 가장 위와 가장 아래에서 카드를 빼고 있다. 그래서 양 끝에서 push와 pop이 가능한 덱(deq) 자료구조를 사용해 문제를 풀었다. 미리 1, 2, ... , N으로 정렬된 덱을 만들고, 수열 A에서 반복문을 돌며 기술 1, 2, 3을 정반대로 수행하면 된다. 덱을 사용해야 한다는 점만 안다면 어렵지 않은 문제였다.

 

코드

#include <iostream>
#include <deque>
#define MAX 1000001
using namespace std;

int N;
int A[MAX];
deque<int> d, answer;

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
}

int main() {
	int temp1, temp2;

	init();
	cin >> N;
	for (int i = 0; i < N; i++) {
		d.push_back(i+1);
	}
	for (int i = 0; i < N; i++) cin >> A[i];

	for (int i = N - 1; i >= 0; i--) {
		switch (A[i]) {
		case 1:
			temp1 = d.front();
			d.pop_front();
			answer.push_back(temp1);
			break;
		case 2:
			temp1 = d.front();
			d.pop_front();
			temp2 = answer.back();
			answer.pop_back();
			answer.push_back(temp1);
			answer.push_back(temp2);
			break;
		case 3:
			temp1 = d.front();
			d.pop_front();
			answer.push_front(temp1);
			break;
		}
	}

	while (!answer.empty()) {
		cout << answer.back() << " ";
		answer.pop_back();
	}

	return 0;


}