[백준,c++] 2346번 - 풍선 터뜨리기

문제

2346번: 풍선 터뜨리기

 

코드

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    deque<pair<int,int>>dq; //{점수, 인덱스};
    vector<int>ans;
    
    int N; cin>>N;
    
    for(int i=0; i<N; i++){
        int num; cin>>num;
        dq.push_back({num,i});
    }
    
    while(!dq.empty()){
        int num = dq.front().first;
        int index = dq.front().second;
        ans.push_back(index+1);
        dq.pop_front();
        
        for (int i = 1; i < num; i++) {
            dq.push_back(dq.front());
            dq.pop_front();
            
        }
        for (int i = 0; i > num; i--) {
            dq.push_front(dq.back());
            dq.pop_back();
            
        }
    }
   
    for(int i: ans) cout<<i<<' ';
}

 

풀이(풀이 시간: 50분)

원형 큐 문제였습니다. 이번에 확실하게 원형 큐가 어떠한 원리로 돌아가게 되는지 이해할 수 있게 도와준 문제였습니다.

원형 큐 개념에 관해서는 위 영상을 참고했습니다.

문제 풀이가 오래 걸린 이유는 풍선 이동시 아래와 같은 이동을 해야 하는데 왼쪽으로 이동할 때에도 [숫자 - 1] 만큼 이동하여 계속 디버깅하느라 오래 걸렸습니다. 

• 오른쪽으로 이동시:  [숫자 -1] 만큼 이동
• 왼쪽으로 이동시: [숫자]만큼 이동