[BOJ] 2346번 풍선 터뜨리기 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        Deque<Balloon> dq = new ArrayDeque<>();

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            dq.add(new Balloon(i + 1, Integer.parseInt(st.nextToken())));
        }

        // 첫 풍선 터트리고 시작
        Balloon first = dq.pollFirst();
        int num = first.num;
        sb.append(first.idx).append(" ");

        while (!dq.isEmpty()) {
            Balloon now = null;

            if (num < 0) {
                // 음수인 경우 왼쪽으로 이동하는 것을 구현 -> 덱의 뒤에서 빼서 앞으로 옮긴다.
                for (int i = 0; i < -num; i++) {
                    dq.offerFirst(dq.pollLast());
                }

                // 왼쪽으로 이동할 경우, 터져야 할 풍선은 현재 맨 뒤에 위치함
                now = dq.pollFirst();
                num = now.num;
            } else {
                // 양수인 경우 오른쪽으로 이동하는 것을 구현 -> 덱의 앞에서 빼서 뒤로 옮긴다.
                for (int i = 0; i < num; i++) {
                    dq.offerLast(dq.pollFirst());
                }

                // 오른쪽으로 이동할 경우, 터져야 할 풍선은 현재 맨 앞에 위치함
                now = dq.pollLast();
                num = now.num;
            }

            sb.append(now.idx).append(" ");
        }

        System.out.println(sb);
    }

    static class Balloon {
        int idx;
        int num;

        public Balloon(int idx, int num) {
            this.idx = idx;
            this.num = num;
        }
    }
}

📄 해설

접근

• 원형으로 풍선이 있고, 1번의 왼쪽에 N번이, N번의 오른쪽에 1번이 있다는 것, 터진 풍선을 빼고 이동하는 것, 오른쪽과 왼쪽 모두로 이동하는 것 => 덱을 사용해야하는 문제로 접근
• 덱을 사용한다는 접근을 했다면, 접근은 90% 끝났다고 생각한다. 나머지 10%는 다음과 같다.
  • 양수인 경우 오른쪽으로 이동한다. => dq.offerFirst(dq.pollLast())
  • 음수인 경우 왼쪽으로 이동한다. => dq.offerLast(dq.pollFirst())
• 접근을 다 했다면 큰 무리없이 해결이 가능했을 것이다.

과정

• N 을 입력받고, 덱을 생성한다. 이때, 풍선의 번호와 종이에 적힌 숫자를 표현하기 위해 Balloon 이라는 클래스를 만들어 사용했다. (길이가 2인 배열을 사용해도 된다.)
• 첫 번째 풍선은 먼저 터트리고 출력해준다.
• 덱이 빌 때까지, 종이에 적힌 숫자에 따라 풍선을 덱에서 꺼내고 출력하면 되는데, 이때 유의할 점은 총 3칸을 움직인 경우, 터트려야 할 풍선도 같이 이동해있는 상태이기 때문에, num이 음수일 경우 맨 앞의 풍선을 꺼내고, 양수일 경우 맨 뒤의 풍선을 꺼내준다.