[백준] 2346번 - 풍선 터트리기 - Java

 

Deque 를 이용해서 풀었습니다.

Deque 객체를 생성할 때 구현체를 LinkedList 로 하니 메모리 초과가 발생합니다.

LinkedList 가 아닌 ArrayDeque 로 생성해줘야 합니다.

풍선의 인덱스와 다음에 터트릴 풍선으로 가는 이동 횟수를 저장하기 위해 풍선 클래스를 생성해

풍선 객체를 Deque 의 요소로 갖게 했습니다. 가장 먼저 터트리는 풍선을 미리 꺼내서 풍선 인덱스를 StringBuiler 에

추가하고 이동 횟수를 초기화시킵니다. 이동 횟수가 양수면 앞에 요소를 빼서 뒤에 추가하고 음수면 뒤에 요소를 빼서

앞에 추가합니다. 이동 횟수만큼 이동했을 때는 Deque 에 추가하지 않고 풍선 인덱스를 StringBuiler 에 추가하고

이동 횟수를 초기화시킵니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class p2346 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

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

        Deque<Balloon> q = new ArrayDeque<>();
        for(int i=1; i< n+1; i++) {
            q.offerLast(new Balloon(i, Integer.parseInt(st.nextToken())));
        }

        Balloon balloon = q.pollFirst();
        sb.append(balloon.index +" ");
        int nextBalloon = balloon.paperNum;

        while (!q.isEmpty()){
            if(nextBalloon > 0) {
                for(int j=0; j<nextBalloon-1; j++){
                    q.offerLast(q.pollFirst());
                }
                balloon = q.pollFirst();
                sb.append(balloon.index +" ");
                nextBalloon = balloon.paperNum;
            } else {
                for(int j=0; j<Math.abs(nextBalloon)-1; j++){
                    q.offerFirst(q.pollLast());
                }
                balloon = q.pollLast();
                sb.append(balloon.index +" ");
                nextBalloon = balloon.paperNum;
            }
        }
        System.out.println(sb);
    }

    static class Balloon {
        int index;
        int paperNum;

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