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

 

 

 

 

문제 출저

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

2346번: 풍선 터뜨리기

 

 

 

문제 풀이

 풍선의 갯수와 풍선 안에 숫자가 주어집니다. 

풍선 안에 숫자는 양수와 음수로 양수면 오른쪽부터 세고, 음수면 왼쪽으로 셉니다. 

셈을 마친 풍선을 터뜨리고 해당 풍선의 숫자만큼 반복합니다.

1번부터 풍선을 터뜨렸을 때, 어떤 순서로 풍선들이 터지는지 구해야 합니다. 

 

Deque를 이용해 문제를 풀었습니다. 

양수인 경우 해당 숫자만큼 처음에서 빼서 끝에 넣었습니다. (오른쪽 이동 표현)

음수인 경우 해당 숫자만큼 마지막에서 빼서 처음에 넣었습니다. (왼쪽 이동 표현)

정답을 List에 담아 출력했습니다. 

 

 

 

소스 코드

package baekjoon.backjoon12.day0110.day10;

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

/*
풍선 터뜨리기
https://www.acmicpc.net/problem/2346
 */

public class B2346 {

  static int n;
  static Deque<Ballon> ballons;

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine());

    ballons = new ArrayDeque<>();

    StringTokenizer st = new StringTokenizer(br.readLine());
    for(int i = 0; i < n; i++) {
      int index = i+1;
      int number = Integer.parseInt(st.nextToken());

      ballons.addLast(new Ballon(index, number));
    }

    List<Integer> answer = new ArrayList<>();
    Ballon ballon = ballons.poll();
    answer.add(ballon.index);
    int number = ballon.number;

    while(!ballons.isEmpty()) {
      if(number > 0) {
        int count = number - 1;
        while(count-- > 0) {
          ballons.addLast(ballons.pollFirst());
        }
        ballon = ballons.pollFirst();
        answer.add(ballon.index);
        number = ballon.number;
      }
      else if(number < 0) {
        int count = (number * -1) -1;
        while(count-- > 0) {
          ballons.addFirst(ballons.pollLast());
        }
        ballon = ballons.pollLast();
        answer.add(ballon.index);
        number = ballon.number;
      }
    }

    for(int data : answer) {
      System.out.print(data + " ");
    }

  }

  public static class Ballon {
    int index;
    int number;

    Ballon(int index, int number) {
      this.index = index;
      this.number = number;
    }

  }

}