https://www.acmicpc.net/problem/2346
문제
> 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고,
i번 풍선의 오른쪽에는 i+1번 풍선이 있고,
왼쪽에는 i-1번 풍선이 있다.
> 단, 1번 풍선의 왼쪽에 N번 풍선이 있고,
N번 풍선의 오른쪽에 1번 풍선이 있다.
> 각 풍선 안에는 종이가 하나 들어있고,
종이에는 -N보다 크거나 같고,
N보다 작거나 같은 정수가 하나 적혀있다.
> 이 풍선들을 다음과 같은 규칙으로 터뜨린다.
> 우선, 제일 처음에는 1번 풍선을 터뜨린다.
> 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다.
> 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다.
> 이동할 때에는 이미 터진 풍선은 빼고 이동한다.
> 예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자.
> 이 경우 3이 적혀 있는 1번 풍선,
-3이 적혀 있는 4번 풍선,
-1이 적혀 있는 5번 풍선,
1이 적혀 있는 3번 풍선,
2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.접근
deque를 사용해서 원형 큐를 구현한다.
큐에 배열로 처음 풍선의 번호, 풍선안에 있는 번호를 쌍으로 저장한다.
맨처음 1번 풍선을 터뜨리고 내부의 수에 쓰여진 대로 deque를 돌린다.
이때, 터뜨린다(poll)하면 자동으로 뒤에 있는 원소들이 앞으로 오게 되어 오른쪽으로 한칸 이동한 형태가 되므로 쓰여진 숫자가 양수면 해당 수 -1 만큼 이동하고, 음수면 그대로 그 수만큼 이동한다.
문제해결
> 풍선수 N을 입력받고 Deque를 선언하는데 번호, 쓰인 수를 저장하기 위해 int[]형으로 선언한다.
> i는1 부터 풍선의 번호를 같이 입력받아 저장한다.
> 맨 앞에 있는 풍선을 fdq라고 하고 일단 1번 풍선을 터뜨린다.
> 1번 풍선의 번호 1을 출력하고 안에 있는 수를 fdq[1]로 넘긴다.
> 모든 풍선이 터질때까지 while문을 돌며 fdq[1]의 값에 따라 돌린다.
> 양수면 오른쪽으로 돌리기 위해 fdq값 -1만큼 맨앞의 원소를 뒤로 보낸다.
> 음수면 맨 뒤의 원소를 앞으로 가져온다.
> 다 회전 시킨 뒤, 맨앞에 있는 원소(풍선)을 터뜨리고 번호를 출력하며 들어있는 수를 다시 fdq[1]로 넘긴다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//2346번 풍선 터뜨리기
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
int N = Integer.parseInt(br.readLine());
Deque<int[]> dq = new ArrayDeque<>();
st = new StringTokenizer(br.readLine());
for(int i = 1; i <= N; i++) dq.offer(new int[]{i, Integer.parseInt(st.nextToken())});
int[] fdq = dq.pollFirst();
sb.append(fdq[0]).append(' ');
while(!dq.isEmpty()) {
if(fdq[1] < 0) {
for(int i = 0; i < Math.abs(fdq[1]); i++) dq.offerFirst(dq.pollLast());
}
else if(fdq[1] > 0) {
for(int i = 0; i < Math.abs(fdq[1]) - 1; i++) dq.offerLast(dq.pollFirst());
}
fdq = dq.pollFirst();
sb.append(fdq[0]).append(' ');
}
System.out.print(sb);
}
}
후기
큐에 쌍으로 번호, 들어있는 수를 넣어야만 이번에 터진 풍선의 번호를 알 수 있을것 같았다. 배열이나 쌍 등으로 원소를 가지게 하는게 익숙하지 않아 문법이 좀 어렵게 느껴진다.
