백준 2346 <풍선 터뜨리기>

2346번: 풍선 터뜨리기 (acmicpc.net)

2346번: 풍선 터뜨리기

우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.

예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.

 

일단 각 풍선에 할당되어 있는 종이에 적힌 숫자가 중요하겠다. 여기서 양수가 적혀있을 때는 오른쪽, 음수가 적혀 있을때는 왼쪽이라 했는데, 일단 문제의 포인트가 원형으로 놓여져있다고 해서 약간 어렵다고 처음엔 느낄수있으나, 

사실 이걸 일직선으로 두고보아도 크게 상관없다.  자바에선 덱 (DEQUE) = DOUBLE ENDED QUEUE.를 구현하기에 이 자료구조를 활용하면 원형의 문제를 일직선으로 두고 풀 수 있다.

 

즉 , 종이에 적혀있는 수가 양수일때는 덱의 맨 앞 기준을 두어 문제를 해결하고 종이에 적혀있는 수가 음수일때는 맨 뒤를 기준으로 두어서 문제를 풀 수 있다.

 

아이디어)

 

1.  먼저 큰 반복문은 덱안에 있는 정수가 있을동안은 반복되어야하니 while문을 이용하면 되겠다.

 

2. 일단 덱 안에는 풍선들을 순서대로 집어넣는다. 1,2,3,4,5 형태로 deq이 존재한다.

 

3. 그러면 1이 먼저 지워질것이고 이는 deq의 맨앞에 존재하겠다. 주어지는 종이의 숫자는 1,2,3,4,5을 key로 한 map을 만들어 value에 넣어놓는다.

 

4. 1이 지워진 이후, 이 종이의 숫자 만큼 이동하여, 다음 지워질 숫자가 결정될텐데 이를 담을 변수 moving을 생성한다.

 그렇다면 당연히 첫번째 moving이 담을 값은 1이겠다.

 

5.  또한 moving에 할당된 map의 value, 를 howmuchmove라는 변수에다가 담아둔다.

 이 howmuchmove동안 deq안에 있는 숫자들을 앞으로, 혹은 뒤로 옮길 것이다.

 

6. 여기서 옮긴다는 것이 포인트인데, 우리는 deq에 들어있는 수들을 옮겨 결과적으로 지워져야할 수가 맨 앞 혹은 맨 뒤에 위치하도록 조정할 것이다. 그 이유는 deq의 특성상 맨 앞 혹은 맨 뒤를 제거 할 수 있다. 

 

7. 따라서 종이에 적힌 수가 양수면 맨 앞의 값을 제거하고, 음수면 맨 뒤를 제거할 수 있게  설계를 한다면, 둘이 겹쳐서 오류가 나는 걸 방지하며 원형으로 된 구조를 일자 구조로 보기에 쉽다. 

 

package 스택과큐;
import java.io.*;
import java.util.*;
public class _2346_풍선터뜨리기 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		ArrayDeque<Integer> deq = new ArrayDeque<Integer>();
		HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st =  new StringTokenizer(br.readLine());
		
		for(int i=1; i<=n; i++) {
			deq.addLast(i);
		}
		
		for(int i=1; i<=n; i++) {
			map.put(i, Integer.parseInt(st.nextToken()) );
			}
		int moving =1;
		while(!deq.isEmpty()) {
			int howmuchmove = map.get(moving);
			//System.out.println("howmuchmove "+howmuchmove);
			sb.append(moving+" ");
			deq.remove(moving);
			if(!deq.isEmpty()) {
				if(howmuchmove >0) {
					for(int i=0; i<howmuchmove-1; i++) {
						deq.addLast(deq.removeFirst());
					}
					moving = deq.peekFirst(); //standard..
					
				}
				else {
					for(int i=0; i<Math.abs(howmuchmove)-1; i++) {
						deq.addFirst(deq.removeLast());
					}
					moving = deq.peekLast();
					
				}
				
			}
			
			
		
			
		}
		System.out.println(sb);
		
		

	}

}