문제 출처

단계별로 풀어보기 > 스택 큐 덱 > 풍선 터뜨리기
https://www.acmicpc.net/problem/2346

문제 설명

1~N번까지의 N개의 풍선이 원형으로 있을 때, 풍선 안에는 값이 들어있는 종이가 있다.
종이에 적힌 값만큼 움직여 다음 풍선을 터뜨린다.
이 과정을 풍선 모두 터뜨릴 때까지 반복하고, 그 순서를 출력하라.

접근 방법

Deque를 이용하여 구현한다.
풍선을 터뜨렸을 때, 안의 값이 음수이면 초기값 -1 부터 해당 수 이전까지 이동한다(감소하여).
한 번 이동할 때마다 Deque 맨 뒤의 값을 poll하여 맨 앞으로 offer 한다.
해당 수 이전까지 이동했으면 pollLast를 하여 값을 뽑는다.
풍선을 터뜨렸을 때, 안의 값이 양수이면 초기값 +1 부터 해당 수 이전까지 이동한다(증가하여).
한 번 이동할 때마다 Deque 맨 앞의 값을 poll하여 맨 뒤로 offer 한다.
해당 수 이전까지 이동했으면 pollFirst를 하여 값을 뽑는다.

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class 풍선_터뜨리기 {

    public static class Balloon {

        private int index;
        private int paper;

        public Balloon(int index, int paper) {
            this.index = index;
            this.paper = paper;
        }

        public int getIndex() {
            return index;
        }

        public int getPaper() {
            return paper;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        Deque<Balloon> dq = new ArrayDeque<>();

        for (int i = 0; i < N; i++) {
            Balloon b = new Balloon(i + 1, Integer.parseInt(st.nextToken()));
            dq.addLast(b);
        }

        StringBuilder sb = new StringBuilder();

        Balloon balloon1 = dq.pollFirst();

        int paper = balloon1.getPaper();

        sb.append(balloon1.getIndex()).append(" ");
        Balloon rs;
        while (dq.size() != 1) {

            if (paper < 0) {
                for (int i = -1; i > paper; i--) {
                    dq.offerFirst(dq.pollLast());
                }
                rs = dq.pollLast();
            } else {
                for (int i = 1; i < paper; i++) {
                    dq.offerLast(dq.pollFirst());
                }
                rs = dq.pollFirst();
            }

            sb.append(rs.getIndex()).append(" ");
            paper = rs.getPaper();
        }

        sb.append(dq.poll().getIndex());

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class 풍선_터뜨리기_review {

    public static class Ballon{

        public int index;
        public int paper;

        public Ballon(int index, int paper){
            this.index = index;
            this.paper = paper;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        Deque<Ballon> dq = new ArrayDeque<>();

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

        StringBuilder sb = new StringBuilder();

        Ballon bl = dq.pollFirst();
        int paper = bl.paper;

        sb.append(bl.index).append(" ");

        while(dq.size() != 1){
            if(paper < 0){
                for(int i = -1; i>paper; i--){
                    dq.offerFirst(dq.pollLast());
                }
                bl = dq.pollLast();
                sb.append(bl.index).append(" ");
                paper = bl.paper;
            } else {
                for(int i = 1; i<paper; i++){
                    dq.offerLast(dq.pollFirst());
                }
                bl = dq.pollFirst();
                sb.append(bl.index).append(" ");
                paper = bl.paper;
            }

        }

        sb.append(dq.poll().index);

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

초기값 i의 설정을 잘 못하여 그 지점에서만 20분동안 해맸다.
종이의 값이 음수로 나온 경우 초기값을 -1, 양수로 나온 경우 초기값을 1로 지정해야 각각 맞는 연산을 할 수 있다.

문제푼 흔적

Review