[BaekJoon] 2346번 - 풍선 터뜨리기 [Java][C++]

문제 링크

---

1. 문제 풀이

$1$ 번부터 $N$ 번까지의 풍선이 있고 각 풍선에 다음 풍선까지 이동하는 종이가 있을 때 터지는 순서를 구하는 문제로 풍선이 원형으로 놓인 점과 왼쪽이나 오른쪽으로 이동하면서 찾아야 한다는 점에서 덱 자료구조를 활용했다. 첫 번째 풍선부터 현재 풍선을 터뜨리고 양수면 덱의 앞 풍선을 덱의 뒤로, 음수면 덱의 뒷 풍선을 덱의 앞으로 숫자만큼 이동시키면 된다. 이때 매번 덱의 앞 풍선을 터뜨리게 구현했는데 이 때문에 양수일 때는 종이에 적힌 숫자보다 한 번 덜 옮겨서 터뜨릴 풍선이 덱의 가장 앞에 오게, 음수면 숫자만큼 이동에서 터뜨릴 풍선이 덱의 가장 앞에 오게 했다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        Deque<int[]> dq = new ArrayDeque<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            int x = Integer.parseInt(st.nextToken());
            dq.offerLast(new int[]{i, x});
        }

        while (true) {
            int[] balloon = dq.pollFirst();

            sb.append(balloon[0]).append(" ");

            if (dq.isEmpty()) break;

            int x = balloon[1];
            if (x > 0) {
                for (int i = 1; i < x; i++) {
                    dq.offerLast(dq.pollFirst());
                }
            } else {
                for (int i = 1; i <= -x; i++) {
                    dq.offerFirst(dq.pollLast());
                }
            }
        }

        System.out.println(sb);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    deque<pair<int, int>> dq;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        dq.push_back({i, x});
    }

    while (true) {
        auto p = dq.front();
        dq.pop_front();

        cout << p.first << ' ';

        if (dq.empty()) break;

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

---