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

 

문제

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

N개의 풍선이 일렬로 나열되어 있고, 각 풍선에는 숫자가 적혀 있습니다. 첫 번째 풍선부터 시작하여 풍선을 터뜨리고, 그 풍선에 적힌 숫자만큼 왼쪽이나 오른쪽으로 이동해 다음 풍선을 터뜨립니다. 모든 풍선을 터뜨릴 때까지 이 과정을 반복합니다.

접근 방법

Deque를 사용하여 양쪽 끝에서 삽입과 삭제가 가능하기 때문에 풍선을 터뜨린 후 이동하는 작업을 효율적으로 처리할 수 있다.

 

풀이 과정

• 첫 번째 풍선을 터뜨리고, 그 풍선의 값을 기록합니다.
• 그 값을 기준으로 오른쪽(양수) 또는 왼쪽(음수)으로 이동합니다.
• 이동한 후에 다음 풍선을 터뜨리고, 그 값을 다시 기록합니다.
• 이 과정을 모든 풍선이 터질 때까지 반복합니다.

 

코드

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

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

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

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

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

        int[] balloonLocation = new int[N];
        for (int i = 0; i < N; i++) {
            balloonLocation[i] = Integer.parseInt(st.nextToken());
        }

        br.close();
        sb.append("1 ");
        int moveValue = balloonLocation[0];

        for(int i = 1; i < N; i++){
            queue.add(new Balloon(i+1, balloonLocation[i]));
        }

        while(!queue.isEmpty()){
            if(moveValue > 0){
                for(int i = 1; i < moveValue; i++){
                    queue.add(queue.poll());
                }

                Balloon next = queue.poll();
                moveValue = next.numValue;
                sb.append(next.index+" ");
            } else{
                for(int i = 1; i < -moveValue; i++){
                    queue.addFirst(queue.pollLast());
                }

                Balloon next = queue.pollLast();
                moveValue = next.numValue;
                sb.append(next.index).append(" ");
            }
        }

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

class Balloon {
    int index;
    int numValue;

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

메모리:16632kb 시간:164ms