[백준] 2346 풍선 터뜨리기 - Java / Python

 

 

 

요세푸스 문제처럼 덱을 사용해서 원을 구현하고 풀이하는 문제다.

 

인덱스 값과 몇 번 띄어넘는지 알려주는 값을 함께 넣어야 하므로 따로 클래스를 만들고 클래스를 덱에 넣어줬다.

(여기서 배열을 사용할 수도 있을 것 같다.)

 

List에 항상 기본형 타입만 넣는다는 생각은 버리자!!

 

그 다음부터는 한 칸 씩 당겨주면서 해결하면 되는데...

cycle이 양수일 때는 poll을 진행하면서 이미 한 칸 당겨졌기때문에 한 번 덜 당겨져야 한다.

 

Java

 

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		Deque<array> dq = new ArrayDeque<>();

		for(int i=1; i<N+1; i++){
			dq.add(new array(i, Integer.parseInt(st.nextToken())));
		}

		while(true){
			if(dq.size()==1){
				break;
			}
			array temp = dq.pollFirst();
			int cycle = temp.cycle;
			sb.append(temp.index).append(" ");

			if(cycle < 0) { // 음수일 때
				while(cycle++ < 0)
						dq.addFirst(dq.pollLast());
		} else { // 양수일 때는 한 칸 덜 이동해야 한다.
				cycle = cycle -1; 
				while(cycle-- > 0)
						dq.addLast(dq.pollFirst());
		}

		}

		sb.append(dq.poll().index);

		System.out.println(sb);
		



		

	}

	static class array{
		int index = 0;
		int cycle = 0;

		array(int a, int b){
			index = a;
			cycle = b;
		}
	}
}

 

Python

 

파이썬으로는 훨씬 쉽게 풀 수 있다.

 

enumerate로 튜플을 생성해 바로 덱에 적용할 수 있고

deque의 rotate함수를 사용해서 덱의 회전을 쉽게 구현할 수 있다.

 

from collections import deque
from operator import index

N = int(input())
dq = deque(enumerate(map(int,input().split(" ")), start=1))
ans = []

while dq:
    index, cycle = dq.popleft()
    ans.append(index)
    if cycle>0:
        dq.rotate(-(cycle-1))
    else:
        dq.rotate(-cycle)

for i in ans:
    print(i, end=" ")