[BOJ] #2346 풍선 터뜨리기

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

2346번: 풍선 터뜨리기

---

덱을 활용하여 양방향에서 접근이 가능하게끔 풀어내야 하는 문제다. 이때 주의해야할 점은, 주어지는 종이에 적힌 수(코드상에서는 k라 정의함)가 양수인지 음수인지에 따라서 다르게 처리를 해주어야 한다는 점이다. 필자 또한 양수 음수에 따라 조건문으로 분기된 상황에서 반복횟수를 잘못 설정해 어려움을 겪었다. 

기본적으로 양끝단 두 곳 모두 접근이 가능한 자료구조를 사용해야 하기에 덱을 사용했지만, 그냥 벡터를 쓰고 pop_back() 대신에 erase를 써도 될 것 같다. vector.erase(vector.end() - 1) 이런식으로. end() - 1을 해주는 이유는 end 자체가 맨 마지막 인자 다음 포인터를 리턴하는 값이기 때문에 거기서 1을 빼서 마지막 인자 그 자체로 접근가능하게 만들어 주어야 한다. 벡터를 쓰던 덱을 쓰던간에 이때 사용하는 자료구조는 pair형으로 선언하여 풍선의 번호와 종이에 적힌 수 둘 모두를 처리할 수 있도록 해야한다.

처음에 코드를 짤 때는 풍선의 번호를 따로 저장하는 vector를 만들어 처리했지만, 그냥 while문을 돌면서 바로바로 출력하도록 고쳤다. 문제에서 메모리 제한이 4MB이기에 혹시라도 메모리 초과로 틀리는일이 없게끔 말이다.

처음에 삽질때문에 실버문제인데도 불구하고 푸는데 한 30분가량? 넘게? 걸린것 같다. 더 분발해서 이정도 문제는 간단히 풀 수 있도록 연습하자.

#include <iostream>
#include <deque>

using namespace std;

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

    int N;
    cin >> N;

    deque<pair<int, int>> dq;

    for (int i=0; i<N; i++) {
        int a;
        cin >> a;
        dq.push_back(make_pair(i+1, a));
    }

    while(1) {
        cout << dq.front().first << ' ';
        int k = dq.front().second;
        dq.pop_front();

        if (dq.empty()) return 0;
        
        if (k>0) {
            for (int i=0; i<k-1; i++) {
                dq.push_back(dq.front());
                dq.pop_front();
            }
        }
        else {
            for (int i=0; i<(-1*k); i++) {
                dq.push_front(dq.back());
                dq.pop_back();
            }
        }
    }

    return 0;
}