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

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

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이다.

출력

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

 

풀이

결과 카드인 1~n까지의 수가 순서대로 있다고 가정하고 각 기술들을 거꾸로 수행한다

1. 제일 위의 카드 1장을 바닥에 내려놓는다. -> 카드를 맨 위로 넣는다
2. 위에서 두 번째 카드를 바닥에 내려놓는다. -> 카드를 위에서 두번째 위치로 넣는다
   -> 맨 위 카드 pop 수행후 해당 카드를 push하고 pop했던 카드 다시 push
3. 제일 밑에 있는 카드를 바닥에 내려놓는다. -> 카드를 제일 밑으로 넣는다

카드를 위에 넣었다가 밑에 넣었다가 방향이 왔다갔다 하므로 양방향인 덱을 사용해보자

 

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <stack>
#include <deque>

using namespace std;
    
int main() {
    int n;
    cin >> n;
    stack<int> skills;
    for(int i=0; i<n; i++) {
        int input;
        cin >> input;
        skills.push(input);
    }
    deque<int> ans;
    
    for(int i=1; i<=n; i++){  // i번째 수행때는 i번 카드를 움직인다
        int skill = skills.top();
        skills.pop();  // 스킬을 최근것부터 꺼내서 거꾸로 수행
        
        switch (skill) {
            case 1:  // 제일 위의 카드 1장을 바닥에 내려놓는다. -> i 카드를 맨 위로 넣는다
                ans.push_front(i);
                break;
                
            case 2:  // 위에서 두 번째 카드를 바닥에 내려놓는다. -> i 카드를 위에서 두번째 위치로 넣는다
            {
                int top_card = ans.front();
                ans.pop_front();
                ans.push_front(i);
                ans.push_front(top_card);
                break;
            }
                
            case 3:  // 제일 밑에 있는 카드를 바닥에 내려놓는다. -> i 카드를 제일 밑으로 넣는다
                ans.push_back(i);
                break;
        }
    }
    
    while(!ans.empty()){
        cout << ans.front() << " ";
        ans.pop_front();
    }
    
    return 0;
}

/*
 */

 

solution함수 버전 (프로그래머스)

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <stack>
#include <deque>

using namespace std;

deque<int> solution(int n, stack<int> &skills) {
    deque<int> ans;
    
    for(int i=1; i<=n; i++){  // i번째 수행때는 i번 카드를 움직인다
        int skill = skills.top();
        skills.pop();  // 스킬을 최근것부터 꺼내서 거꾸로 수행
        
        switch (skill) {
            case 1:  // 제일 위의 카드 1장을 바닥에 내려놓는다. -> i 카드를 맨 위로 넣는다
                ans.push_front(i);
                break;
                
            case 2:  // 위에서 두 번째 카드를 바닥에 내려놓는다. -> i 카드를 위에서 두번째 위치로 넣는다
            {
                int top_card = ans.front();
                ans.pop_front();
                ans.push_front(i);
                ans.push_front(top_card);
                break;
            }
                
            case 3:  // 제일 밑에 있는 카드를 바닥에 내려놓는다. -> i 카드를 제일 밑으로 넣는다
                ans.push_back(i);
                break;
        }
    }
    

    return ans;
}

int main() {
    int n;
    cin >> n;
    stack<int> skills;
    for(int i=0; i<n; i++) {
        int input;
        cin >> input;
        skills.push(input);
    }
    
    deque<int> ans = solution(n, skills);
    
    while(!ans.empty()){
        cout << ans.front() << " ";
        ans.pop_front();
    }
    
    return 0;
}

/*
 */