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

문제 : 2346

풀이 point

덱을 활용하여 풀이를 진행할 수 있다.
풍선의 번호를 출력해야하므로 덱 안에 pair를 두거나 덱 2개를 둘 수 있다.

풀이 방법

덱을 활용하여 종이에 적혀 있는 수가 양수라면 수만큼 이동할때까지 앞에 있는 요소들을 뒤로 옮긴다. 음수라면 뒤에 요소를 앞으로 옮긴다. 이동 수만큼 이동했다면 요소를 삭제 후 다시 이동 수를 설정해준다.

코드

//백준 2346, 풍선 터뜨리기
#include <iostream>
#include <deque>

std::deque<int> d;
std::deque<int> idx;

int main(){
    int N, n;
    std::cin >> N;

    for(int i{0}; i<N; ++i){
        std::cin >> n;
        d.push_back(n);
        idx.push_back(i+1);
    }

    int turn{d.front()};
    std::cout << idx.front() << ' ';
    d.pop_front();
    idx.pop_front();
    int cnt = turn > 0 ? 1 : -1;

    while(!d.empty()){
        if(turn < 0){
            if(cnt == turn){
                std::cout << idx.back() << ' ';
                turn = d.back();
                d.pop_back();
                idx.pop_back();
                cnt = turn > 0 ? 1 : -1;
            }
            else{
                d.push_front(d.back());
                d.pop_back();
                idx.push_front(idx.back());
                idx.pop_back();
                --cnt;
            }
        }
        else if(turn > 0){
            if(cnt == turn){
                std::cout << idx.front() << ' ';
                turn = d.front();
                d.pop_front();
                idx.pop_front();
                cnt = turn > 0 ? 1 : -1;
            }
            else{
                d.push_back(d.front());
                d.pop_front();
                idx.push_back(idx.front());
                idx.pop_front();
                ++cnt;
            }
        }
    }

    return 0;
}