2346번: 풍선 터뜨리기
첫째 줄에 자연수 N(1≤N≤1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 편의상 0은 적혀있지 않다고 가정하자.
www.acmicpc.net
list의 첫번째 풍선을 터뜨리고 안에 적혀있는 수에 맞게 이동하여 다음 풍선을 터뜨리고, 최종적으로 풍선을 터뜨리는 순서를 구하는 문제입니다.
저는 덱을 이용하였습니다. 풍선을 터뜨릴 위치는 무조건 덱의 맨 앞입니다.
그러면 다음 위치를 찾아서 맨 앞으로 가져다 놓아야합니다.
풍선에 적혀있는 수가 양수면 오른쪽으로 이동하는 것인데
덱의 맨 앞의 숫자를 맨 뒤로 보내는 것으로 해결할 수 있습니다.
하지만 양수가 적혀있는 풍선을 터뜨리면 이미 한칸은 오른쪽으로 이동한 것이기 때문에 숫자-1만큼만 이동시킵니다.
풍선에 적혀있는 수가 음수면 왼쪽으로 이동합니다.
덱의 맨 뒤의 숫자를 맨 앞으로 보내는 것으로 해결할 수 있습니다.
마지막 풍선까지 터뜨리고 덱이 비어있으면 break를 해주고 답을 출력합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static Deque<int[]> dq = new ArrayDeque<>();
static int N;
static void func() {
for (int i = 0; i < N; i++) {
int next = dq.peekFirst()[0];
sb.append(dq.peekFirst()[1] + " ");
dq.removeFirst();
if (dq.isEmpty())
break;
if (next > 0) {
next--;
while (next-- > 0) {
dq.addLast(dq.peekFirst());
dq.removeFirst();
}
} else {
while (next++ < 0) {
dq.addFirst(dq.peekLast());
dq.removeLast();
}
}
}
System.out.println(sb.toString());
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
dq.addLast(new int[] { Integer.parseInt(st.nextToken()), i });
}
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 6416 트리인가? (0) | 2021.02.04 |
|---|---|
| boj 3190 뱀 (0) | 2021.02.02 |
| boj 5397 키로거 (0) | 2021.02.02 |
| boj 10866 덱 (0) | 2021.02.02 |
| boj 11000 강의실 배정 (0) | 2021.02.01 |