백준 2346번: 풍선 터뜨리기

N개의 풍선이 원형으로 놓여있을 때, 특정 규칙에 따라 풍선을 터뜨리고 이동하는 과정을 시뮬레이션하는 문제입니다. 원형 구조를 효율적으로 흉내 낼 수 있는 덱(Deque) 자료구조를 사용하는 것이 문제 해결의 핵심입니다.

---

✅ 문제 개요

항목	내용
문제 번호	2346번 - 풍선 터뜨리기
난이도	실버 3
핵심 알고리즘	자료구조, 덱(Deque), 시뮬레이션

---

✅ 문제 설명 요약

• 입력:
  1. 첫째 줄: 풍선의 개수 N (1 ≤ N ≤ 1,000)
  2. 둘째 줄: 1번부터 N번까지의 풍선 안에 들어있는 종이의 숫자
• 출력: 터진 풍선의 번호를 순서대로 공백으로 구분하여 출력
• 규칙:
  1. 1번 풍선을 먼저 터뜨립니다.
  2. 터진 풍선 안의 종이에 적힌 수만큼 이동하여 다음 풍선을 터뜨립니다.
  3. 양수이면 오른쪽(시계방향), 음수이면 왼쪽(반시계방향)으로 이동합니다.
  4. 이미 터진 풍선은 건너뛰고 이동합니다.

---

✅ 풀이 전략

이 문제는 원형으로 나열된 데이터에서 원소를 제거하고, 제거된 위치를 기준으로 다시 순회를 시작하는 전형적인 시뮬레이션 문제입니다. 이러한 '원형' 구조는 덱(Deque)을 사용하면 매우 효과적으로 구현할 수 있습니다.

1️⃣ 핵심 자료구조: 덱 (Deque)

• 덱은 양쪽 끝에서 데이터를 자유롭게 추가하고 삭제할 수 있습니다.
• 오른쪽 이동(시계방향): 덱의 맨 앞 원소를 꺼내(pollFirst) 맨 뒤에 넣는(addLast) 동작으로 흉내 낼 수 있습니다.
• 왼쪽 이동(반시계방향): 덱의 맨 뒤 원소를 꺼내(pollLast) 맨 앞에 넣는(addFirst) 동작으로 흉내 낼 수 있습니다.

2️⃣ 데이터 저장: Balloon 클래스

• 우리는 각 풍선의 '원래 번호(인덱스)'와 그 안에 적힌 '이동할 칸 수(값)'를 모두 기억해야 합니다.
• 이 두 정보를 함께 관리하기 위해, index와 value를 멤버 변수로 갖는 간단한 Balloon 클래스(또는 int[])를 만드는 것이 좋습니다.

3️⃣ 알고리즘 설계

1. Balloon 객체들을 담을 Deque를 생성합니다.
2. N개의 풍선 정보를 입력받아 (인덱스, 값)을 Balloon 객체로 만들어 Deque에 순서대로 넣습니다.
3. 첫 번째 풍선(#1)을 pollFirst()로 터뜨리고, 그 번호를 결과에 기록합니다. 터진 풍선 안의 값을 다음 이동을 위한 move 변수에 저장합니다.
4. Deque가 빌 때까지 while 반복문을 실행합니다.
   • move가 양수일 경우:
     • move - 1번 만큼 deque.addLast(deque.pollFirst())를 반복하여 덱을 회전시킵니다.
     • 회전이 끝나면 다음 터뜨릴 풍선이 덱의 맨 앞에 위치하게 됩니다.
   • move가 음수일 경우:
     • abs(move) - 1번 만큼 deque.addFirst(deque.pollLast())를 반복하여 덱을 반대 방향으로 회전시킵니다.
     • 회전이 끝나면 다음 터뜨릴 풍선이 덱의 맨 뒤에 위치하게 됩니다.
5. 다음 풍선을 터뜨리고(pollFirst 또는 pollLast), 그 번호를 결과에 기록한 후, 그 안의 값을 다음 move 변수에 업데이트합니다.
   • (로직의 일관성을 위해, 항상 터뜨릴 풍선을 맨 앞으로 가져온 뒤 pollFirst() 하는 것이 더 깔끔합니다.)

예시: N=5, [3, 2, 1, -3, -1]
1. 초기 덱: [(1,3), (2,2), (3,1), (4,-3), (5,-1)]
2. 1번 풍선 터뜨림. 결과: 1. move = 3.
3. move > 0이므로 오른쪽으로 2번(3-1) 회전 -> (2,2), (3,1)이 뒤로 감.
4. 덱 상태: [(4,-3), (5,-1), (2,2), (3,1)]. 맨 앞의 4번 풍선 터뜨림. 결과: 1 4. move = -3.
5. move < 0이므로 왼쪽으로 2번(|-3|-1) 회전 -> (3,1), (2,2)가 앞으로 옴.
6. 덱 상태: [(2,2), (3,1), (5,-1)]. 맨 앞의 2번 풍선 터뜨림. 결과: 1 4 2. move = 2.
7. ... 반복

---

✅ Java 코드 예제

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.ArrayDeque;
import java.util.Deque;

// 풍선 정보를 저장할 클래스
class Balloon {
    int index;
    int value;

    public Balloon(int index, int value) {
        this.index = index;
        this.value = value;
    }
}

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

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        Deque<Balloon> dq = new ArrayDeque<>();
        for (int i = 1; i <= N; i++) {
            dq.add(new Balloon(i, Integer.parseInt(st.nextToken())));
        }

        // 첫 번째 풍선은 무조건 터뜨림
        Balloon current = dq.pollFirst();
        sb.append(current.index).append(" ");
        int move = current.value;

        while (!dq.isEmpty()) {
            if (move > 0) { // 양수일 경우, 앞에서 빼서 뒤로
                // move-1 만큼 회전
                for (int i = 0; i < move - 1; i++) {
                    dq.addLast(dq.pollFirst());
                }
                current = dq.pollFirst();
            } else { // 음수일 경우, 뒤에서 빼서 앞으로
                // abs(move)-1 만큼 회전
                for (int i = 0; i < -move - 1; i++) {
                    dq.addFirst(dq.pollLast());
                }
                current = dq.pollLast();
            }
            sb.append(current.index).append(" ");
            move = current.value;
        }

        bw.write(sb.toString());

        bw.flush();
        bw.close();
        br.close();
    }
}

---

⚠️ 실전 주의사항

항목	설명
데이터 묶기	인덱스와 값을 함께 다뤄야 할 때는 사용자 정의 클래스나 Pair를 사용하는 것이 좋습니다. 이는 코드의 가독성을 높이고 실수를 줄여줍니다.
덱(Deque)의 순환	오른쪽 이동은 addLast(pollFirst()), 왼쪽 이동은 addFirst(pollLast())로 구현하는 것이 덱을 원형처럼 사용하는 핵심 테크닉입니다.
이동 횟수	K만큼 이동할 때, K번째 풍선을 터뜨리려면 K-1번만 회전해야 한다는 점에 유의해야 합니다. (양수 이동 시)
로직 통일	양수, 음수 이동 시 터뜨리는 위치가 달라 헷갈릴 수 있습니다. 이동 방향에 맞게 회전시킨 후, 항상 맨 앞(pollFirst)의 풍선을 터뜨리는 것으로 로직을 통일하면 코드가 더 간결해집니다.

---

📝 마무리 요약

✔️ 원형으로 배치된 데이터를 순서대로 제거하는 문제는 덱(Deque)으로 시뮬레이션하는 것이 매우 효과적입니다.
✔️ 풍선의 원래 번호와 이동할 칸 수를 함께 저장할 객체(클래스)를 활용합니다.
✔️ 양수(오른쪽) 이동은 addLast(pollFirst())를, 음수(왼쪽) 이동은 addFirst(pollLast())를 반복하여 구현합니다.
✔️ 다음에 터뜨릴 풍선을 항상 덱의 맨 앞으로 가져온 후 pollFirst()하는 방식으로 로직을 통일하면 구현이 쉬워집니다.