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

문제

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

18115번: 카드 놓기

 

 

사용한 알고리즘

2022.01.27 - [PS/Algorithm] - [알고리즘 개념정리] 5. 선형 자료구조(스택,큐,덱)

-> 덱

 

 

 

풀이

위에서도 버리고 아래에서도 버릴 수 있는 자료구조인 덱을 사용해야 한다.
기술들을 뒤에서부터 보면서 역연산을 수행하며 1~N을 덱에 담으면 카드의 처음 상태를 알 수 있다.

1. 기술들을 벡터 v에 입력받고 거꾸로 뒤집어준다.(reverse)
2. 벡터 v를 순회하며 기술에 따라 1~N까지 순서대로 덱에 담아준다.
   1번 기술이라면 숫자를 덱의 맨 앞에 넣는다.
   2번 기술이라면 숫자를 덱의 맨 앞에서 두 번째에 넣는다.
   3번 기술이라면 숫자를 덱의 맨 뒤에 넣는다.
3. 덱에 담긴 원소들을 순서대로 출력한다. 

 

 

 

소스코드

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

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n; cin>>n;
    vector <int> v;
    for(int i=0; i<n; i++){
        int x; cin>>x;
        v.push_back(x);
    }
    // 1. 기술들을 벡터 v에 입력받고 거꾸로 뒤집어준다.
    reverse(v.begin(),v.end());
    // 기술을 거꾸로 살펴보면서 1~N을 덱에 넣어줄 것이기 때문!

    deque<int> dq;
    for(int i=0; i<n; i++){
        if(v[i]==1){ // 2. 1번 기술이라면 숫자를 덱의 맨 앞에 넣는다.
            dq.push_front(i+1);
        }
        else if(v[i]==2){ // 2. 2번 기술이라면 숫자를 덱의 맨 앞에서 두번째에 넣는다.
            int tmp=dq.front(); dq.pop_front();
            dq.push_front(i+1);
            dq.push_front(tmp);
        }
        else{ // 2. 3번 기술이라면 숫자를 덱의 맨 뒤에 넣는다.
            dq.push_back(i+1);
        }
    }
    // 3. 덱에 담긴 원소들을 순서대로 출력한다. 
    while(n--){
        cout<<dq.front()<<" ";
        dq.pop_front();
    }
    return 0;
}