백준 2346 풍선 터뜨리기 - JAVA

2346 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

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));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));                  int input = Integer.parseInt(br.readLine());         Deque<Ball> deque = new ArrayDeque<>();         int[] arr = new int[input];         StringBuilder sb = new StringBuilder();                  StringTokenizer st = new StringTokenizer(br.readLine());         for(int i = 1; i <= input; i++) {             int num = Integer.parseInt(st.nextToken());             arr[i-1] = num;             deque.offer(new Ball(num, i));         }                  sb.append(1).append(" ");                  int bombNum = arr[0];         deque.pollFirst();                  while(!deque.isEmpty()) {             if(bombNum > 0) {                 for(int i = 1; i < bombNum; i++) {                     deque.offer(deque.poll());                 }                 Ball next = deque.poll();                 bombNum = next.value;                 sb.append(next.index).append(" ");             } else {                 for(int i = 1; i < -bombNum; i++) {                     deque.offerFirst(deque.pollLast());                 }                 Ball next = deque.pollLast();                 bombNum = next.value;                 sb.append(next.index).append(" ");             }         }         bw.write(sb.toString());         bw.flush();     } }   class Ball {     int value;     int index;          public Ball(int value, int index) {         this.value = value;         this.index = index;     } } Colored by Color Scripter

cs

 

알고리즘 설명

---

해당 문제는 풍선에 적혀있는 숫자만큼 다음 풍선으로 이동하기 때문에,
숫자를 직선이 아닌 원형으로 연결된 것처럼 생각하면 풀이법을 쉽게 생각할 수 있습니다.
풍선에 적힌 수가 양수이면 오른쪽 / 음수이면 왼쪽이므로,
 
양수일 경우에는 원소에 적혀있는 숫자에서 1을 뺀만큼(이미 터진 풍선은 빼고 이동), 맨 앞의 원소를 제거하고, 첫번째 원소에 적힌 숫자만큼 맨 앞의 원소를 제거하고, 제거한 원소를 맨 뒤에 다시 삽입합니다.(다음 원소는 맨 앞 원소)
 
음수일 경우에는 반대로 맨 뒤의 원소를 제거하고, 제거한 원소를 맨 앞에 다시 삽입합니다.(다음 원소는 맨 뒤 원소)
앞뒤로 삽입과 삭제가 가능한 자료구조인 덱을 활용하는것이 핵심입니다.

 

코드 해석

---

풍선에 적힌 숫자를 입력받아 배열과 덱에 저장합니다. 덱의 인덱스는 1-base-position으로 저장합니다.
배열의 첫번째 원소를 bombNum(터뜨릴 풍선)에 저장하고, 덱의 첫번째 원소도 pollFirst로 제거합니다.
덱의 size가 0이 될때까지,

• 양수일 경우, 해당 숫자에서 1을 뺀만큼 맨 앞 원소를 맨 뒤로 이동한 뒤, 이동이 끝나면 맨 앞의 원소를 제거하고 제거된 원소의 value를 다음 bombNum으로 설정합니다.
• 음수일 경우, 해당 숫자에서 1을 뺀 맨 뒤 원소를 맨 앞으로 이동한 뒤, 이동이 끝나면 맨 뒤의 원소를 제거하고 제거된 원소의 value를 다음 bombNum으로 설정합니다.