[백준_2346/JAVA] 풍선 터트리기

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

 

문제풀이

이 문제는 데크의 구조를 이해하고 있어야한다.

원형으로 풍선들이 배치되어있고,

이미 터진 풍선을 제외한 남은 풍선들 사이에서 이동(회전)하는 과정을 구현하기에 데크가 적합하다.

 

int[]로 [풍선 번호, 풍선 속의 번호 종이]의 형태로 저장된다.

- poll(), pollLast()를 통해 오른쪽, 왼쪽으로 필요한 만큼 이동 시키고 그 위치에 있는 풍선을 터트린다.

- 터뜨린 풍선의 종이 값을 다음 이동에 사용해 다음 풍선을 터트림

 

코드

public class Main {
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	int N=Integer.parseInt(br.readLine());
    	int[] arr=new int[N];
    	
    	StringTokenizer st=new StringTokenizer(br.readLine());
    	Deque<int[]> deque=new ArrayDeque<>();
    	
    	for(int i=0;i<N;i++) {
    		arr[i]=Integer.parseInt(st.nextToken());
    	}
    	
    	StringBuilder sb=new StringBuilder();
    	sb.append("1 ");
    	
    	int in=arr[0];
    	
    	for(int i=1;i<N;i++) {
    		deque.add(new int[] {(i+1), arr[i]}); //{풍선 인덱스, 내용}
    	}
    	while(!deque.isEmpty()) {
    		if(in>0) {
    			for(int i=1;i<in;i++) {
    				deque.add(deque.poll());
    			}
    			int[] next=deque.poll();
    			in=next[1]; // 풍선 속의 내용
    			sb.append(next[0]+ " ");
    		}
    		else {
    			for(int i=1;i<-in;i++) {
    				deque.addFirst(deque.pollLast());
    			}
    			int[] next=deque.pollLast();
    			in=next[1];
    			sb.append(next[0]+" ");
    		}
    	}
    	
    	bw.write(sb.toString());
    	bw.flush(); bw.close();
    }
    
}