[BOJ] 2346 풍선 터뜨리기

풍선 터뜨리기

풀이

• 1~N개의 풍선이 원형으로 놓여있다.
  • i번 풍선의 오른쪽에는 i+1번 풍선이, 왼쪽에는 i-1번 풍선이 있다.
• 제일 처음에 1번 풍선 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어, 그 종이에 적혀있는 값만큼 이동한다. 양수일 때는 오른쪽, 음수일때는 왼쪽.
• 예를 들어, [3,2,1,-3,-1] 이 적혀있으면, 3이 적혀있는 1번 풍선 -> -3이 적혀 있는 4번 풍선 -> -1이 적혀 있는 5번 풍선 -> 1이 적혀 있는 3번 풍선-> 2가 적혀있는 2번 풍선 순으로 터진다.
• 원형큐면 덱으로 풀자. 덱을 몰랐더니 오래 걸림.. 하지만 덱을 안다면? 10분컷 쌉가능
  • 양수가 나왔어? 그러면 앞에 N개를 뽑아서 뒤에 순서대로 넣으면 됨.
    • deq.offer(deq.poll())
  • 음수가 나왔어? 그러면 뒤에 N개를 뽑아서 앞에 순서대로 넣으면 됨.
    • deq.offerFirst(dq.pollLast())

🙆‍♀️ 정답 풀이

import java.util.*;
import  java.io.*;
public class BOJ2346 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Deque<int[]> queue = new ArrayDeque<>();
        StringTokenizer st= new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for(int i=0;i<N;i++){
            int num =  Integer.parseInt(st.nextToken());
            queue.offer(new int[]{num,i+1});
            arr[i] = num;
        }
        StringBuilder sb = new StringBuilder();
        int[] first = queue.poll();   //첫번째꺼 빼기
        sb.append(first[1]+" ");
        int cnt = first[0];
        while(!queue.isEmpty()){
            if(cnt>0){
                for(int k=1;k<cnt;k++){
                    queue.add(queue.poll());
                }
                int[] nxt = queue.poll();// 앞에꺼 빼기
                cnt= nxt[0];
                sb.append(nxt[1]+" ");
            }
            else{
                for(int k=1;k<-cnt;k++){
                    queue.addFirst(queue.pollLast());
                }
                //뒤에꺼 빼기
                int[] nxt = queue.pollLast();
                cnt = nxt[0];
                sb.append(nxt[1]+" ");
            }
        }
        System.out.println(sb);
    }
}