백준 2346 - 풍선 터뜨리기
Updated:
Java
2346 번 - 풍선 터뜨리기
문제
N개의 풍선이 있다. 각 풍선 안에는 -N부터 N까지의 수가 적혀있는 종이가 들어 있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.
우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 풍선은 원형으로 놓여 있다고 생각한다. 즉, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있는 것이다. 이동할 때에는 이미 터진 풍선은 빼고 생각한다.
예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.
문제 출처
접근 방법
문제의 목표는 모든 풍선을 터뜨리되, 각 풍선을 터뜨릴 때 마다 해당하는 풍선을 기준으로 좌 우로 탐색하여 그 풍선을 제거하는 것이다.
풍선이 없어지면 빈 자리는 당연히 없어지며, 이는 터진 풍선은 이동할 때 제외한다.
위 2개의 조건을 생각하면 문제를 해결하기에 적합한 방법은 stack과 queue가 합쳐진 deque을 사용하는 것이다.
각 풍선을 터뜨린 후 나온 정수가 양수이면 앞의 풍선을 뒤로 보내는 방법으로, 음수이면 뒤의 풍선을 앞으로 보내는 방식으로 다음 터뜨릴 풍선을 찾는다.
구현
자바에는 pair 구조체가 없는 것 같아 Pair 클래스를 만들어 deque의 자료형으로 두었다. key는 풍선의 값 그리고 value는 처음 위치를 두어 풍선이 터질 때 마다 처음 위치를 출력하게 해주었다.
key가 양수이면 풍선 리스트 제일 앞에서 뒤로 보내면서 다음 풍선을 찾는다.
음수면 반대이고, 이후 풍선을 pop(poll)하여 제거한다.
코드
/*
2346번 - 풍선 터뜨리기
https://www.acmicpc.net/problem/2346
*/
import java.util.*;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String []args) throws IOException {
//System.setIn(new FileInputStream("res/mainInput.txt")); //제출 할 때 주석
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Deque<Pair> deq = new ArrayDeque<>();
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 1; i <= n; i++)
deq.add(new Pair(Integer.parseInt(st.nextToken()),i));
int curN = 0; //처음 터뜨릴 풍선은 제일 앞이므로 0이다.
for(int i = 0; i < n; i++) {
if(curN >=0) { //다음 터뜨릴 풍선이 오른쪽에 있는 경우
for(int j = 0; j < curN - 1; j++) {
deq.add(deq.pollFirst()); // 앞을 pop하여 뒤에 넣는다.
}
curN = deq.getFirst().key;
System.out.print(deq.getFirst().value + " ");
deq.pollFirst(); //이후 제일 앞의 풍선을 pop한다.
}
else { //다음 터뜨릴 풍선이 왼쪽에 있는 경우
for(int j = 0; j < Math.abs(curN + 1); j++) {
deq.addFirst(deq.pollLast()); // 역으로 뒤의 풍선을 pop하여 앞으로 보낸다.
}
curN = deq.getLast().key;
System.out.print(deq.getLast().value + " ");
deq.pollLast();
}
}
br.close();
}
public static class Pair{ // Pair 구현
int key;
int value;
Pair(int k,int v){
key = k;
value = v;
}
int getKey() {
return key;
}
int getValue() {
return value;
}
// Pair를 사용하는 구조체가 제대로 입력 되었는지 확인하기 위함
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("Pair [key=").append(key).append(", value=").append(value).append("]");
return builder.toString();
}
}
}
총평
난이도
⭐⭐⭐★★
후기
처음에는 배열의 인덱스를 하나씩 탐색하려 하였지만, 코드가 굉장히 복잡해지며 해결하지 못하였다. stack / queue / deque 문제들을 뜸하게 풀었더니, 해당 구조체를 쓸 생각을 전혀 못하였다.
위 문제와 같이 대상을 제거하며 오른쪽, 왼쪽으로 이동하여 다음 대상을 제거하거나 탐색하려는 문제는 위 3개의 구조체를 생각하도록 기억해둔다.
개선할 점
없
