[백준/C++] 2346번 풍선 터뜨리기

1.문제 링크

2346

2. 풀이 전 계획과 생각

• 자료구조 덱 이용하기

3. 풀이

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

int main(){
    int n; cin>>n;
    deque<pair<int, int> > dq;
    
    for(int i=0;i<n;i++){
        int temp; cin>>temp;
        dq.push_back({temp,i+1});
    }
    
    while(!dq.empty()){
        int temp = dq.front().first;
        int index=dq.front().second;
        dq.pop_front();
        cout<<index<<' ';
        if(dq.size()!=0){
            if(temp>0){
                for(int i=0;i<temp-1;i++){
                    dq.push_back(dq.front());
                    dq.pop_front();
                }
            }
            else{
               temp = -temp;
               for(int i=0;i<temp;i++){
                    dq.push_front(dq.back());
                    dq.pop_back();
                } 
            }
        }
    }
}

자료구조 덱에 {숫자, 인덱스}로 저장한다. 그리고 숫자가 0보다 큰경우, 작은 경우로 나누어 덱 연산을 하고, pop할 때마다 덱의 second 즉 인덱스를 출력한다.

4. 풀이하면서 고민했던 점

5. 문제를 풀고 알게된 개념 및 소감

• c++ stl 덱(Deque) 사용법을 알게되었다.