백준18115 - 카드 놓기

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

18115번: 카드 놓기

deque를 이용하여 해결한 문제이다. deque를 선택한 이유는 문제에서는 맨 앞이나 맨 뒤나 맨 뒤에서 2번째 수를 뽑아내는 연산을 하고 있어서 deque를 선택하였다. 주어진 입력과 반대로 거슬러 올라가면서 추리한다. 

 

주어진 입력이 1인 경우는 맨 뒤에 원소를 넣어준다.

 

주어진 입력이 2인 경우는 맨 뒤에 원소를 빼내어 어딘가에 저장해두었다가 현재 넣어야 하는 수를 맨 뒤에 넣고 다시 빼낸 원소를 맨 뒤에 넣는다.

 

주어진 입력이 3인 경우는 맨 앞에 원소를 넣어준다.

 

주어진 원소의 시작은 1로 설정한다. 왜냐하면 5 4 3 2 1에서 마지막으로 뽑히는 원소는 1이기 때문이다. 

#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, x;
    int input;
    vector<int> v;
    deque<int> dq;
    
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> x;
        v.push_back(x);
    }
    
    input = 1;
    
    reverse(v.begin(), v.end());
    
    for(int i = 0; i < n; i++) {
        if(v[i] == 1) {
            dq.push_back(input);
        }
        else if(v[i] == 2) {
            int temp = dq[dq.size() - 1];
            dq.pop_back();
            dq.push_back(input);
            dq.push_back(temp);
        }
        else if(v[i] == 3) {
            dq.push_front(input);
        }
        input++;
    }
    
    while(!dq.empty()) {
        cout << dq[dq.size() - 1] << ' ';
        dq.pop_back();
    }
}