백준 2346: 풍선 터뜨리기(java)

문제

---

풀이

 

큐의 양 끝에서 삽입과 삭제가 일어나므로 덱을 사용한다.

덱 객체 생성하는 부분에서 LinkedList를 업캐스팅하면 메모리가 초과되므로 ArrayDeque를 사용해야 한다.

Deque 인터페이스 상속 관계 참고

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

풍선의 번호와 풍선의 내용물 2개의 변수가 함께 변화해야 하므로, 풍선의 번호와 내용물 정보를 저장하는 Balloon 클래스를 작성했다.

int[] balloonValue=new int[N];
	for(int i=0; i<N; i++) {
		balloonValue[i]=Integer.parseInt(st.nextToken());
}
for(int i=1; i<N; i++) {
	deque.addLast(new Balloon(i+1, balloonValue[i]));
}

읽어들인 풍선 내용물 숫자를 저장하는 balloonValue 배열을 생성하고, 덱에 Balloon 객체를 삽입한다.

두 번째 for문에서 i=1부터 시작하는 이유는 첫 번째 풍선은 무조건 터뜨리고 시작하기 때문이다.

 

이제 풍선 번호와 내용물(=다음 이동거리)을 갱신해야 하는데, 내용물이 양수일 때와 음수일 때 각각 반대로 동작한다.

//move=이동 거리(직전에 터뜨린 풍선 내용물)
if(move>0) {
	for(int i=1; i<move; i++) {
		deque.addLast(deque.removeFirst());
   	}
	Balloon nextBalloon=deque.removeFirst();
	move=nextBalloon.value;	//이동할 값
	sb.append(nextBalloon.index+" ");
}

move가 양수일 때는 for문을 이용하여 다음에 터뜨릴 풍선의 바로 앞 풍선까지 반대쪽으로 이동시킨 후, 그 다음 터뜨릴 Balloon 객체인 nextBalloon 객체를 생성해 주고 move 값을 갱신한다.

else {
	for(int i=1; i<-move; i++) {
		deque.addFirst(deque.removeLast());
	}
	Balloon nextBalloon=deque.removeLast();	//이동할 값
	move=nextBalloon.value;
	sb.append(nextBalloon.index+" ");
}

 

move가 음수일 때는 양수일 때와 반대로 계산해 주면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		Deque<Balloon> deque=new LinkedList<>();
		StringBuilder sb=new StringBuilder();
		
		int N=Integer.parseInt(br.readLine());
		StringTokenizer st=new StringTokenizer(br.readLine());
		int[] balloonValue=new int[N];	//풍선 내용물
		for(int i=0; i<N; i++) {
			balloonValue[i]=Integer.parseInt(st.nextToken());
		}
		
       		 //1번 풍선 터뜨리고 시작
		sb.append("1 ");
		int move=balloonValue[0];	//이동 거리
		
		for(int i=1; i<N; i++) {
			deque.addLast(new Balloon(i+1, balloonValue[i]));
		}
		
		while(!deque.isEmpty()) {
			if(move>0) {
				for(int i=1; i<move; i++) {
					deque.addLast(deque.removeFirst());
				}
				Balloon nextBalloon=deque.removeFirst();
				move=nextBalloon.value;	//이동할 값
				sb.append(nextBalloon.index+" ");
			}
			else {
				for(int i=1; i<-move; i++) {
					deque.addFirst(deque.removeLast());
				}
				Balloon nextBalloon=deque.removeLast();	//이동할 값
				move=nextBalloon.value;
				sb.append(nextBalloon.index+" ");
			}
		}
		System.out.println(sb);
	}
}