문제
N개의 풍선이 원형으로 배치되어 있고 각 풍선에 종이가 들어있다. 1번 풍선을 터뜨린 후, 종이에 적힌 수만큼 이동하여 다음 풍선을 터뜨리는 과정을 반복할 때, 터지는 순서를 구하라.
입력
첫째 줄에 N (1 ≤ N ≤ 1000), 둘째 줄에 각 풍선의 종이 값이 주어진다. 양수면 오른쪽, 음수면 왼쪽으로 이동.
출력
터지는 풍선의 번호를 순서대로 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 3 2 1 -3 -1 | 1 4 5 3 2 |
풀이
Deque를 원형 큐처럼 활용하여 회전과 제거를 시뮬레이션한다.
- 1번 풍선을 먼저 터뜨리고, 2번부터 N번까지를 Deque에 넣는다
- 양수(오른쪽): (값-1)번 앞에서 빼서 뒤로 넣은 후 앞에서 제거
- 음수(왼쪽): (|값|-1)번 뒤에서 빼서 앞으로 넣은 후 뒤에서 제거
- 제거된 풍선의 종이 값으로 다음 이동 방향과 거리를 결정한다
핵심 아이디어: Deque의 양방향 삽입/제거를 활용하면 원형 배열에서의 회전을 효율적으로 시뮬레이션할 수 있다.
코드
package day499;
import java.io.*;
import java.util.*;
public class Day468BOJ2346풍선터뜨리기 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Deque<int[]> q = new ArrayDeque<>();
StringTokenizer st = new StringTokenizer(br.readLine());
int[] arr = new int[n];
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++)
q.add(new int[] { (i + 1), arr[i] });
while (!q.isEmpty()) {
if (in > 0) {
for (int i = 1; i < in; i++)
q.add(q.poll());
int[] nxt = q.poll();
in = nxt[1];
sb.append(nxt[0] + " ");
} else {
for (int i = 1; i < -in; i++)
q.addFirst(q.pollLast());
int[] nxt = q.pollLast();
in = nxt[1];
sb.append(nxt[0] + " ");
}
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(N * max(|값|)) (각 풍선마다 값만큼 회전)
- 공간: O(N)