백준 2346 풍선 터뜨리기 | Java 덱

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

---

이 문제의 핵심 로직은 위의 사진으로 설명할 수 있다. 터트릴 위치를 지정하는 것을 움직이는 게 아니라, 터트릴 위치는 고정한 채로 전체 덱을 회전시키면서 이동한 것처럼 구현하는 것이다.

이게진짜일리없어...

이 문제는 정말 슬프게도.. 자바스크립트로는 풀 수 없는 문제이다.

찾아보니 자바스크립트로는 풀 수 없는 문제라고 한다 . ..
메모리 제한이 너무 낮다나 뭐라나..

터진 풍선 속에 있는 숫자만큼 값을 넣고 빼는 과정을 반복하며 문제를 해결할 수 있다.

정확히 맞는지는 모르겠지만, 테케는 통과했던 자바스크립트 코드 공유합니다..^_ㅠ

function solution(N, moves) {
  let balloons = [];
  const answer = [];

  for (let i = 1; i <= N; i++) {
    balloons.push(i);
  }

  let i = 0;

  while (balloons.length > 0) {
    const ball = balloons.shift();
    answer.push(ball);

    if (balloons.length === 0) {
      break;
    }

    const move = moves[ball - 1];

    if (move > 0) {
      for (let j = 0; j < (move % balloons.length) - 1; j++) {
        balloons.push(balloons.shift());
      }
    } else {
      for (let j = 0; j < Math.abs(move % balloons.length); j++) {
        balloons.unshift(balloons.pop());
      }
    }
    i++;
  }

  return answer;
}

// =====입출력=====

const fs = require("fs");
const input = fs.readFileSync(0, "utf-8").trim().split("\n");

const count = Number(input[0]);
const moves = input[1].split(" ").map(Number);

const answer = solution(count, moves);
console.log(answer.join(" "));

자바로 풀어보자!

그래도 처음 짤 때보단 나았다. 이미 로직은 어느정도 확실해진 상태이고, 언어만 바꾸면 됐기 때문!
게다가 자바에는 덱이 이미 구현되어있다면서요?..
나만 힘든 싸움을 했던거야,

하지만 기대와 다르게..

어떻게 고쳐봐도 틀렸다. 왜 틀렸지????

어떻게 해도 틀리던 코드는 아래와 같다.

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

public class Main {
    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());

        // 입력
        int[] moves = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            moves[i] = Integer.parseInt(st.nextToken());
        }

        Deque<Integer> balloons = new LinkedList<>();

        // 풍선 덱 초기화
        for(int i = 1; i <= N; i++){
            balloons.add(i);
        }

        while(!balloons.isEmpty()){
            int balloon = balloons.removeFirst();
            sb.append(balloon).append(" ");

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

            int move = moves[balloon - 1];

            if(move > 0){
                for(int j = 0 ; j < move - 1 ; j++){
                    balloons.addLast(balloons.removeFirst());
                }
            } else {
                for(int j = 0 ; j < Math.abs(move); j++) {
                    balloons.addFirst(balloons.removeLast());
                }
            }
        }

        System.out.println(sb.toString().trim());

    }
}

문제점

스터디원들과 머리를 맞대고 고민해봤는데, 아무리 생각해도 로직은 맞았다.

덱을 Linked List로 선언한 부분이 가장 의심스럽다는 결론을 내리고 이 부분을 ArrayDeque으로 수정해봤더니 됐다..

왜?

덱 구현체

자바의 덱 구현체는 ArrayDeque, LinkedList 이렇게 두가지가 있다.
기본적으로 ArrayDeque은 하나의 연속된 배열에 각각 참조를 저장하는 방식이다. 반면에 LinkedList같은 경우에는 모든 요소마다 최소 하나의 노드 객체가 생기고, 객체 내에는 item, prev, next 필드가 포함되어있다.

만약 덱의 사이즈가 5인 경우에, ArrayDeque는 길이가 5인 하나의 배열로 구현이 가능하지만, LinkedList는 노드 객체가 5개로 생성되어 메모리를 더 많이 쓰게 된다.😅

그렇기 때문에 대부분의 경우에는 ArrayDeque를 사용하는 것이 메모리 절약면에서 좋다.