백준 2346번, 풍선 터뜨리기(C, C++)

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

2346번: 풍선 터뜨리기

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

int main(){
    int N;
    deque<pair<int, int>>ballon;

    cin>>N;

    for(int i = 0; i < N; i++){
        int temp;
        cin>>temp;
        ballon.push_back({temp, i+1}); //처음 저장 값은 쪽지 값, 두 번째 저장 값은 풍선의 인덱스 
    }

    while(1){
        cout<<ballon.front().second<<" ";
        int cnt = ballon.front().first;
        ballon.pop_front();
        if(ballon.empty()){
            break;
        }
        if(cnt > 0){
            for(int i = 0; i < cnt-1; i++){
                ballon.push_back(ballon.front());
                ballon.pop_front();
            }
        }else{
            for(int i = cnt; i < 0; i++){
                ballon.push_front(ballon.back());
                ballon.pop_back();
            }
        }
    }
    return 0;       
}

이 문제는 풍선을 터뜨리면 안에 있는 쪽지가 양수와 음수가 있는데, 그 해당하는 값 만큼 이동한다

양수면, 오른쪽으로 음수면 왼쪽으로 이동하게되는데 덱을 이용하여 구현을 하도록 합니다.

덱에 push_back()을 하나 씩 사용하게 되면 위 그림처럼 나타낼 수 있습니다.

2와 3이 pop_front()가 되어 빠져나올 것이고 이를 하단에 넣기위해 push_back()을 이용하여 다시 넣도록합니다.

음수일 때 덱이 어떻게 움직이는 지, 양수일 때 마찬가지로 어떻게 움직이는 지 메커니즘을 위 그림을 통해 알게 되었습니다. 해당 과정을 쪽지의 값대로 덱이 빌 때까지 반복하고 break을 통해 while문을 탈출하도록 하면 출력 값에 고스란히 인덱스의 움직임이 출력됩니다.