[백준] 2346. 풍선 터뜨리기 - Java

🖇️ 문제 링크

2346번: 풍선 터뜨리기

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.

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

 

---

💡 문제 분석

덱 자료구조를 이용해서 앞, 뒤를 연결시켜줍니다.

덱에서 원소를 poll()했을 때, 자동으로 오른쪽으로 한 칸은 이동하기 때문에, 오른쪽으로 이동할 때는 1칸 덜 이동시킵니다.

 

---

⌨️ 코드

import java.util.*;

public class Q2346 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Deque<Balloon> deq = new ArrayDeque<>();
        for(int i = 0; i < n; i++)
            deq.add(new Balloon(i + 1, sc.nextInt()));

        StringBuilder sb = new StringBuilder();

        while(deq.size() > 1) {
            Balloon cur = deq.poll();
            sb.append(cur.idx).append(" ");
            int move = cur.num;
            if(move < 0) {
                while(move++ < 0)
                    deq.addFirst(deq.pollLast());
            } else {
                move--;
                while(move-- > 0)
                    deq.addLast(deq.pollFirst());
            }
        }

        System.out.println(sb.append((deq.poll()).idx));
    }

    static class Balloon {
        int idx, num;

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

 

---

⏱️ 결과

 

 

Uploaded by Notion2Tistory v1.1.0