백준-18115번: 카드 놓기

Boj handle: wlsgur348

18115번: 카드 놓기

앞, 뒤 모두에서 삽입과 제거가 이루어지는 자료구조에는 deque가 있다.

deque를 사용하는데 대표적인 문제라고한다.

두 개의 deque 카드 배열을 준비하고 첫번째는 1부터 N까지 차례대로 넣는다.

처음 상태를 확인하기 위해서는 사용한 기술들을 역순으로 확인하면서 기술의 반대로 실행시키면서 두 번째 카드 배열에 삽입하면 될 것이다.

두번째 카드 배열이름을 result로 하면 아래와 같이 설명할 수 있다.

1. 제일 위의 카드를 바닥에 내려놓은다 -> 제일 뒤에 있는 카드를 result의 맨 앞으로 놓는다.

2.위에서 두번째 카드를 바닥에 내려놓는다 ->첫번째 카드를 빼고 두번째 카드를 result의 맨 앞으로 놓은 후에 첫번째 카드를 다시 앞으로 돌려놓는다.

3.제일 밑에 있는 카드를 바닥에 내려놓는다.->제일 뒤에 카드를 result의 맨 뒤로 놓는다.

다음을 코드로만 옮겨놓으면 해결된다.

#include<iostream>
#include<deque>
using namespace std;
int arr[1000001];
int main() {
	int N;
	cin >> N;
	deque<int>dq;
	deque<int>result;
	for (int i = 0; i < N; i++) {
		dq.push_front(i + 1);
	}
	for (int i = N-1; i >= 0;i--) {
		cin >> arr[i];
	}
	for (int i = 0; i < N; i++) {
		if (arr[i] == 1) {
			result.push_front(dq.back());
			dq.pop_back();
		}
		else if (arr[i] == 2) {
			int tmp = result.front();
			result.pop_front();
			result.push_front(dq.back());
			result.push_front(tmp);
			dq.pop_back();
		}
		else if (arr[i] == 3) {
			result.push_back(dq.back());
			dq.pop_back();
		}
	}
	for (int i = 0; i < N; i++) {
		cout << result[i] << " ";
	}
	return 0;
}