[백준/Java] 2346 : 풍선 터뜨리기

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

 

이번 문제는 단순 자료구조 문제입니다. 풍선에서 나온 값에 따라 마지막 데이터를 제거하고 처음에 추가하거나 처음 데이터를 제거하고 마지막 데이터에 추가하면 됩니다.

 

만약 풍선에 적힌 값이 양수라면 처음 데이터를 제거하고 마지막에 추가하고 음수라면 마지막 데이터를 제거하고 처음에 추가하면 됩니다.

 

여기서 주의할 점은 양수인 경우 풍선이 터지면서 자연스럽게 위 과정을 거치므로 값에서 1을 빼서 진행을 하면 됩니다.

예시를 들어 2 3 1 2 4일 경우 2가 터지면 다음에 숫자는 2를 기준으로 오른쪽 두 칸을 이동한 1이 되어야 하는데 2가 터짐과 동시에 3 1 2 4에 기준이 3으로 바뀌므로 1을 뺀 값을 옮기면 됩니다.

 

여기까지 풀이했을 때 무조건 정답이라고 생각했지만 '메모리 초과'를 받게 되었습니다. 이에 대해서 학습을 해본 결과 Deque의 구현체로는 LinkedList와 ArrayDeque가 있는 것을 알게 되었습니다. 그리고 알게된 2개의 차이점을 설명해보겠습니다.

1. ArrayDeque은 LinkedList와 달리 다음 노드에 대한 참조를 유지할 필요가 없기 때문에 더 적은 메모리를 사용합니다.
2. ArrayDeque은 LinkedList보다 cache-locality에 좀 더 친숙합니다.
3. ArrayDeque의 내부 배열이 가득 차면 크기를 두 배로 늘리고 모든 데이터를 복사해야 하기 때문에 시간이 조금 더 걸립니다.

 

import java.io.*;
import java.util.*;
import java.util.LinkedList;

public class Backjoon_2346_풍선_터뜨리기 {
    public static class Node{
        int idx, value;

        public Node(int idx, int value) {
            this.idx = idx;
            this.value = value;
        }
    }
    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());
        Deque<Node> dq = new ArrayDeque<>();
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 1 ; i <= N ; i++){
            int value = Integer.parseInt(st.nextToken());
            dq.offer(new Node(i, value));
        }

        while(dq.size() > 1){
            Node node = dq.poll();
            int idx = node.idx;
            int value = node.value;

            if(value > 0 ){
                value--;
                for(int i = 0 ; i < value ; i++){
                    dq.offer(dq.poll());
                }
            }else{
                value = Math.abs(value);
                for(int i = 0 ; i < value ; i++){
                    dq.offerFirst(dq.pollLast());
                }
            }
            sb.append(idx + " ");
        }
        sb.append(dq.poll().idx);
        System.out.println(sb);
    }
}