2346 풍선 터뜨리기

1. 풀이

 

덱을 이용해서 풀었다.

 

예제를 가지고 풀이해 보겠다.

 

<예제>

5

3 2 1 -3 -1

 

 

 

1. 입력값 받기

 

코드에서

클래스 Balloon 을 만든다.

변수 number, value 를 갖는다.

number : 풍선 번호, value : 풍선 안 종이에 적혀있는 값

 

위의 예제에서

 

number => 1  2  3  4  5

value =>    3  2  1  -3 -1

 

 

 

일단 입력값을 Balloon 객체에 맞게 만든 뒤  덱 (input) 에 넣는다.

즉, (numver, value) 형태이므로, 

(1,3) (2,2) (3,1) (4,-3) (5,-1) 이 들어감.

 

 

2. while 문

 

 

예시로 설명하면,

 

1) 

현재 덱의 상태는 (1,3) (2,2) (3,1) (4,-3) (5,-1) 이다.

(1,3) 이 덱의 앞쪽, (5,-1) 쪽이 덱의 뒤쪽이다.

풍선이 원형으로 놓여있다고 했으므로 결국 덱의 앞쪽과 뒤쪽이 연결되어 있다고 생각하고 풀면된다.

 

제일 처음에는 1번 풍선을 터뜨린다고 했다.

즉 덱의 맨 앞에 있는 value = 3을 갖는 Balloon 객체

(1,3) 을 덱에서 꺼낸다.

덱에서 꺼낸다는 것은 풍선을 터뜨린다는 것이다.

 

=> 최종 덱 상태 : (2,2) (3,1) (4,-3) (5,-1) 

 

터진 풍선의 번호를 차례대로 정답으로 나열하라고 했으므로

answer(정답) : 1

(일단 1번 풍선만 터뜨렸으므로 1 표시)

 

2) 

위에서 value=3 인 풍선을 터뜨렸고, value가 양수이기 때문에 오른쪽으로 3번 이동한 풍선을 다음으로 터뜨리면 된다.

(2,2)는 오른쪽으로 한 번 이동한 것이고, (3,1)은 두 번, (4,-3) 이 세 번 이동한 것이다.

그러면 (4,-3) 을 덱에서 꺼내야 되는데,

그 앞에 있는 

 

(2,2), (3,1) 은 덱의 앞에서 꺼내서 뒤에 넣어준다.

=> 덱 : (4,-3), (5,-1), (2,2), (3,1)

 

그 후 (4,-3) 을 꺼낸다.

 

=> 최종 덱 상태 : (5,-1), (2,2), (3,1)

answer(정답) : 1,4

 

 

3)

위에서 (4,-3) 을 꺼냈으므로

그 다음 터뜨릴 풍선은

왼쪽으로 3번 이동한 풍선이다.

현재 위치에서 왼쪽으로 한 번 이동하면, (3,1)

왼쪽으로 한 번 더 이동하면 (2,2)

왼쪽으로 한 번 더 이동하면 (5,-1) 이다.

즉, (5,-1) 을 꺼낸다.

 

그런데 이 과정은 2)번 과정이랑 반대이다. 2번은 풍선 오른쪽으로 이동해서, 덱의 앞에서 꺼내서 덱의 뒤에 넣었지만,

여기서는 왼쪽 이동이므로

덱의 뒤에서 Balloon 객체를 꺼내서 덱의 앞에 넣어준다.

 

즉, 현재 덱이

(5,-1), (2,2), (3,1) 상태인데,

 

덱의 뒤에서 Balloon객체를 꺼내서 앞에 넣어주면 

=> 덱 : (3,1), (5,-1), (2,2)

 

덱의 뒤에서 Balloon객체를 꺼내서 앞에 넣어주면 

=> 덱 : (2,2), (3,1), (5,-1)

 

덱의 뒤에서 Balloon객체를 꺼내서 앞에 넣어주면 

=> 덱 : (5,-1), (2,2), (3,1) 이 된다.

 

즉 (5,-1) 을 꺼내면 된다.

 

=> 최종 덱 : (2,2), (3,1)

answer(정답) : 1, 4, 5

이런식으로 진행하면 된다.

 

 

3. 주의할 점

덱을 정의할 떄 LinkedList 사용 시 메모리초과 날 수 있다.

순차적인 데이터 추가, 삭제에는 ArrayList 사용이 효과적이라고 한다.

 

 

2. 최종 코드 

 

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


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


public class Main {

	
	public static void main(String[] args) throws IOException {
		
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		Deque<Balloon> input = new ArrayDeque<>();
		StringBuilder answer = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " " );
		for(int i=1; i<=N; i++) {
			
			input.addLast(new Balloon(i, Integer.parseInt(st.nextToken())));
		}
		
		
	
		boolean check = true;
		
		while(!input.isEmpty()) { 
			
		
			int a = 0;
			
			
			if(check) {
				Balloon b1 = input.removeFirst();
				a =b1.value;
				answer.append(b1.number + " ");
			}else {
				Balloon b2 = input.removeLast();
				a = b2.value;
				answer.append(b2.number + " " );
			}
			
			
			
			if(input.isEmpty()) {
				break;
				
			}else if(a >0) {
				
				check = true;
				
				while(a-->1) {
					input.addLast(input.removeFirst());
				}
				
			}else if(a<0 ) {
				
				check = false;
				
				int M = Math.abs(a);
				while(M-->1) {
					input.addFirst(input.removeLast());
				}
			}
		}
		
		
		
		System.out.println(answer.toString().trim());
	}
}

 

 

참고 블로그 : https://kwoncorin.tistory.com/92

[JAVA]백준 2346번: 풍선 터뜨리기