백준 알고리즘 - 2346번: 풍선 터뜨리기 [Java]

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

2346번: 풍선 터뜨리기

1. 코드

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        Deque <int[]> d = new ArrayDeque<>();
        for(int i = 0; i < N; i++) {
            int[] arr = { i + 1, sc.nextInt() };
            d.add(arr);
        }

        while(d.size() != 1) {
            int[] arr = d.remove();
            sb.append(arr[0]).append(' ');
            int move = arr[1];

            if(move > 0)
                for(int i = 1; i < move; i++)
                    d.add(d.remove());
            else
                for(int i = move; i < 0; i++)
                    d.addFirst(d.removeLast());
        }
        System.out.println(sb.toString() + d.remove()[0]);
    }
}

2. 설명

양쪽 끝에서 제거하거나 추가할 수 있는 덱의 성질을 이용하여 마치 하나로 이어진 것처럼 만들 수 있습니다. 따라서 제일 첫번째 요소의 값이 다음 제거될 순서가 되도록 매순간 만들어 줍니다.

덱의 요소가 1개만 존재할 경우 즉시 반복문을 종료하고 현재 남아있는 덱의 요소를 문자열에 추가하여 출력하면 문제는 해결됩니다.

3. 정리

1. 덱의 활용을 통해서 마치 원형으로 이어진 것처럼 활용 가능