[2346] 풍선 터트리기

문제 개요

---

백준 2346번 문제, 풍선 터뜨리기는 큐(Queue)를 활용하여 풍선이 터지는 순서를 출력하는 문제다. 이 문제는 자료구조와 덱(Deque)의 활용 능력을 테스트하는 데 적합하다. 주어진 풍선 번호와 이동 값을 기반으로 풍선이 터지는 순서를 계산하는 것이 핵심이다.

코드 분석

---

public class BOJ2346 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Deque<int[]> deque = new ArrayDeque<>();
        String[] input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            int[] arr = {i + 1, Integer.parseInt(input[i])};
            deque.add(arr);
        }

        StringBuilder sb = new StringBuilder();

        while (deque.size() > 1) {
            int[] arr = deque.pollFirst();
            sb.append(arr[0]).append((" "));
            int num = arr[1];

            if (num > 0) {
                for (int i = 1; i < num; i++) {
                    deque.offerLast(deque.pollFirst());
                }
            } else {
                for (int i = num; i < 0; i++) {
                    deque.offerFirst(deque.pollLast());
                }
            }
        }

        sb.append(deque.pollFirst()[0]);
        System.out.println(sb);
    }
}

풀이 과정

---

1. 풍선 정보 입력 및 저장:
   • 풍선의 개수 n과 각 풍선의 이동 값을 입력받는다.
   • 풍선 번호와 이동 값을 {번호, 값} 형태의 배열로 저장해 Deque에 추가한다.
2. 풍선 터뜨리기:
   • 가장 앞에 있는 풍선을 제거하고, 그 번호를 결과 문자열에 추가한다.
   • 제거한 풍선의 이동 값을 기준으로:
     • 이동 값이 양수일 경우:
       • 앞에서 pollFirst로 풍선을 꺼내 offerLast로 뒤에 추가한다.
       • 반복 횟수는 move - 1이다.
     • 이동 값이 음수일 경우:
       • 뒤에서 pollLast로 풍선을 꺼내 offerFirst로 앞에 추가한다.
       • 반복 횟수는 |move| - 1이다.
3. 마지막 풍선 처리:
   • 마지막으로 남은 풍선의 번호를 결과 문자열에 추가한다.
4. 결과 출력:
   • 저장한 결과 문자열을 출력해 터뜨린 순서를 표시한다.

소감

---

문제 파악은 금방 했는데 Deque을 응용하는 부분에서 막혀서 이번에는 다른 분이 작성한 코드를 참고하였다. 항상 느끼지만 자료구조의 특성을 이해하고 있다고 해도 잘 다루기 위해서는 역시 많이 풀어봐야 한다. 더 본격적으로 하기 위해 1일 1코테를 블로그에 남기기로 했다.