[Algorithm] boj_2346 (Deque)

문제

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

접근

포인터를 이용하여 풀 수도 있을것 같지만, Deque(덱)을 이용하여 풀 수 있는 문제다.

1. idx와 nextPointer 필드를 가지는 Balloon 클래스를 선언 후, Deque에 차례로 저장한다.

2. 다음에 꺼내야 하는 값이 Deque의 첫번째 요소로 오도록 만든다.
   예를 들어, 예제 1번에서 첫번째 요소 값, 즉 Balloon(1, 3)을 Deque 에서 꺼낸다.

   이때, nextPointer가 양수일때와 음수일때 다르게 처리해야 한다.

   1. 양수일 경우
      -> 맨 앞의 요소부터 nextPointer - 1 만큼 차례로 Deque의 마지막에 넣어준다.

   2. 음수일 경우
      -> 맨 뒤의 요소부터 nextPointer 만큼 차례로 Deque의 앞에 넣어준다.

   두 경우 모두 nextPointer에 해당하는 값이 Deque의 제일 앞으로 오게 된다.

풀이

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

public class boj_2346_deque {

    static int N;
    static Deque<Balloon> deq = new ArrayDeque<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

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

        StringBuilder sb = new StringBuilder();

        while (!deq.isEmpty()) {
            //현재 풍선을 꺼내고, idx 출력
            Balloon balloon = deq.pollFirst();
            sb.append(balloon.idx).append(" ");

            if (deq.isEmpty()) {
                break;
            }

            if (balloon.pointer > 0) {
                for (int i = 0; i < balloon.pointer - 1; i++) {
                    deq.offerLast(deq.pollFirst());
                }
            } else {
                for (int i = 0; i < Math.abs(balloon.pointer); i++) {
                    deq.offerFirst(deq.pollLast());
                }
            }
        }

        System.out.println(sb);
    }

    static class Balloon {
        int idx;
        int pointer;

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