[알고리즘/Java] 백준 2346번: 풍선 터뜨리기

1. 문제

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

2346번: 풍선 터뜨리기

---

2. 연관 알고리즘

• 자료 구조(Data Structures)
• 덱(Deque)

---

3. 풀이

문제 지문 발췌 이미지1.

문제 지문 발췌 이미지2.

• 풍선이 원형으로 놓여있으므로 양방향으로 삽입/제거가 가능한 덱(Deque)을 활용해 상황을 가정할 것이다.
• 터뜨리는 데는 규칙이 따른다: ①첫 번째 풍선을 우선 터뜨리고 → ②해당 풍선에 든 종이에 적힌 값만큼 자리 이동한 뒤 → ③또 한 번 처음에 온 풍선을 터뜨린다. 더 이상 남은 풍선이 없을 때까지 해당 과정을 반복한다.

Deque<int[]> deque = new ArrayDeque<>();

• 덱(Deque)의 타입 자리에는 Integer, Character와 같은 래퍼 클래스(wrapper class)는 물론 String 클래스, 사용자 정의 클래스 등이 올 수 있으며, 이번 문제에서와 같이 배열 또한 취급 가능하다.
• 여기선 양방향으로 추가/삭제가 일어날 뿐, 노드간 연결은 불필요하기에 LinkedList가 아닌 ArrayDeque를 구현체로 삼았다.

int[] numbers = new int[N];
for(int i=0; i < numbers.length; i++) { //array 초기화
	numbers[i] = Integer.parseInt(st.nextToken());
}
for(int i=0; i < N; i++) { //deque 초기화
	deque.offer(new int[] {(i+1), numbers[i]}); //{풍선 고유 index, 풍선에 적힌 번호}
}

• 임의로 주어지는 N개의 숫자를 int[] 배열 numbers에 담아준다.
• 이어서 {풍선 고유 index, 풍선에 적힌 번호} 순으로 new int[] 선언해 deque에 저장한다.
  • 문제에서 요구하는 풍선별 인덱스가 1부터 시작되므로 (i+1) 처리가 필요하다.
  • 따라서 풍선 고유 index는 [0], 풍선에 적힌 번호는 [1]로 각각의 값에 접근할 수 있게 된다.

while(!deque.isEmpty()) {
	int idx = deque.peek()[0]; //프론트 풍선 고유 index
	int num = deque.peek()[1]; //프론트 풍선에 적힌 번호
	//첫 번째 풍선 제거
	if(idx == 1) {
		bw.append(deque.remove()[0] + " ");
		//첫 번째 풍선에 적힌 숫자만큼 자리 이동
		if(num > 0) {
			num -= 1;
			while(num-- > 0) {
				deque.offerLast(deque.pollFirst());
			}
		} else {
			while(num++ < 0) {
				deque.offerFirst(deque.pollLast());
			}
		}
	//다음 인덱스로 이동
	continue;
	} else {
		...
	}
}

• 반복문이 새롭게 시작될 때마다 가장 앞에 있는 프론트(front) 요소의 값을 조회해 idx, num으로 초기화한다.
  • 현재 덱(Deque)에 배열 타입으로 저장돼 있기에 [0]번은 프론트 풍선 고유 index, [1]번은 프론트 풍선에 적힌 번호에 해당한다.

while(!deque.isEmpty()) {
	int idx = deque.peek()[0]; //프론트 풍선 고유 index
	int num = deque.peek()[1]; //프론트 풍선에 적힌 번호
	//첫 번째 풍선 제거
	if(idx == 1) {
		...
	} else {
		bw.append(deque.remove()[0] + " "); //이전 숫자만큼 자리 이동이 완료된 상태이므로 현재 기준 프론트 제거
		if(deque.size() == 0) break; //remove() 치른 후 더 이상 남은 숫자가 없다면 break;
		//양수인 경우 오른쪽으로(앞으로) 이동
		if(num > 0) {
			num -= 1; //프론트를 제거하면서 이미 한 칸씩 앞당겼기 때문에 -1만큼 덜 이동하도록 설정
			while(num-- > 0) {
				deque.offerLast(deque.pollFirst());
			}
		//음수인 경우 왼쪽으로(끝으로) 이동
		} else {
			while(num++ < 0) {
				deque.offerFirst(deque.pollLast());
			}
		}
	}
}

• 주의할 점은 remove() 직후 while문이 이어지므로 덱(deque)에서 가장 마지막 요소까지 제거되거든 더 이상의 탐색 없이 반복문을 탈출할 수 있도록 조건을 걸어둬야 한다: if(deque.size() == 0) break;
• 또한 remove() 통해 기존 프론트가 제거되고 이미 한 칸씩 앞당겼기 때문에, 풍선에 적힌 번호가 양수일 때는 -1만큼 덜 이동하도록 설정이 필요하다: if(num > 0) { num -= 1 }
• 예를 들어 num {3,2,1,-3,-1}이고, idx [1,2,3,4,5]일 때 다음과 같은 연산이 일어난다.
  • 첫 번째 풍선이므로 remove() 3 [idx 1]
    • 3은 양수이므로 오른쪽으로 (3-1)만큼 이동
    • 재정렬된 덱 {-3,-1,2,1}
  • remove() -3 [idx 4]
    • -3은 음수이므로 왼쪽으로 +3만큼 이동
    • 재정렬된 덱 {-1,2,1}
  • remove() -1 [idx 5]
    • -1은 음수이므로 왼쪽으로 +1만큼 이동
    • 재정렬된 덱 {1,2}
  • remove() 1 [idx 3]
    • 1은 양수이므로 (1-1)만큼 이동
    • 재정렬된 덱 {2}
  • remove() 2 [idx 2]
    • (deque.size() == 0)이 되므로 break; 통해 반복문 탈출

---

4. 전체 코드

🌱GitHub(BOJ2346)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		Deque<int[]> deque = new ArrayDeque<>();
		int[] numbers = new int[N];
		for(int i=0; i < numbers.length; i++) { //array 초기화
			numbers[i] = Integer.parseInt(st.nextToken());
		}
		for(int i=0; i < N; i++) { //deque 초기화
			deque.offer(new int[] {(i+1), numbers[i]}); //{풍선 고유 index, 풍선에 적힌 번호}
		}
		
		while(!deque.isEmpty()) {
			int idx = deque.peek()[0]; //프론트 풍선 고유 index
			int num = deque.peek()[1]; //프론트 풍선에 적힌 번호
			//첫 번째 풍선 제거
			if(idx == 1) {
				bw.append(deque.remove()[0] + " ");
				//첫 번째 풍선에 적힌 숫자만큼 자리 이동
				if(num > 0) {
					num -= 1;
					while(num-- > 0) {
						deque.offerLast(deque.pollFirst());
					}
				} else {
					while(num++ < 0) {
						deque.offerFirst(deque.pollLast());
					}
				}
				//다음 인덱스로 이동
				continue;
			} else {
				bw.append(deque.remove()[0] + " "); //이전 숫자만큼 자리 이동이 완료된 상태이므로 현재 기준 프론트 제거
				if(deque.size() == 0) break; //remove() 치른 후 더 이상 남은 숫자가 없다면 break;
				//양수인 경우 오른쪽으로(앞으로) 이동
				if(num > 0) {
					num -= 1; //프론트를 제거하면서 이미 한 칸씩 앞당겼기 때문에 -1만큼 덜 이동하도록 설정
					while(num-- > 0) {
						deque.offerLast(deque.pollFirst());
					}
				//음수인 경우 왼쪽으로(끝으로) 이동
				} else {
					while(num++ < 0) {
						deque.offerFirst(deque.pollLast());
					}
				}
			}
		}
		bw.flush();
		bw.close();
		br.close();
	}
}