[백준/C++] 18115번: 카드 놓기

문제

수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다.

1. 제일 위의 카드 1장을 바닥에 내려놓는다.
2. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.
3. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.

수현이는 처음에 카드 N장을 들고 있다. 카드에는 1부터 N까지의 정수가 중복되지 않게 적혀 있다. 기술을 N번 사용하여 카드를 다 내려놓았을 때, 놓여 있는 카드들을 확인했더니 위에서부터 순서대로 1, 2, …, N이 적혀 있었다!

놀란 수현이는 처음에 카드가 어떻게 배치되어 있었는지 궁금해졌다. 처음 카드의 상태를 출력하여라.

입력

첫 번째 줄에는 N (1 ≤ N ≤ 106)이 주어진다.

두 번째 줄에는 길이가 N인 수열 A가 주어진다. Ai가 x이면, i번째로 카드를 내려놓을 때 x번 기술을 썼다는 뜻이다. Ai는 1, 2, 3 중 하나이며, An은 항상 1이다.

출력

초기 카드의 상태를 위에서부터 순서대로 출력하여라.

풀이

i번째로 카드를 내려놓았을 때 <- 이 파트에서 i가 사용되기 때문에 0 대신 1부터 시작하는 것이 좋다

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

/*
 * 1) 1번 기술 -> 제일 위의 카드 바닥에 내려놓기 -> 제일 앞에 끼워넣기
 * 2) 2번 기술 -> 위에서 두 번째 카드 바닥에 내려놓기 -> 앞에서 두 번째에 끼워넣기
 * 3) 3번 기술 -> 제일 밑에 있는 카드 내려놓기 -> 제일 뒤에 끼워넣기
 * => 앞/뒤 끼워넣기가 있으므로 deque를 쓴다
 */
deque<int> cardGame(int n, vector<int> &card){
    deque<int> dq;

    for(int i=1; i<=n; i++){ //
        switch (card[i]) {
            case 1:
                dq.push_front(i);
                break;
            case 2:
            {
                int x = dq.front();
                dq.pop_front();
                dq.push_front(i);
                dq.push_front(x);
                break;
            }
            case 3:
                dq.push_back(i);
                break;
        }
    }
    return dq;
}

int main() {
    int n;
    cin >> n;

    // 입력
    vector<int> card(n+1, 0);
    for (int i=1; i<=n; i++) // i번째로 카드를 내려놓았을 때 card[i]번 기술을 쓴다 -> 1번째부터 시작하므로 i=1
        cin >> card[i];

    // 연산
    reverse(card.begin()+1, card.end()); // 거꾸로 생각하기 때문에 reverse 사용
    deque<int> dq = cardGame(n, card);

    // 출력
    while(!dq.empty()){
        cout << dq.front() << " ";
        dq.pop_front();
    }

}