백준 2346번 : 풍선 터뜨리기
이번 문제는 직전에 풀었던 요세푸스 문제와 비슷하지만 더 심화된 문제이다.
사실 정해진 원형 큐에서 순서의 자리를 찾는 요세푸스 문제와는 많이 다르다.
공통점이라고 하면 마찬가지로 원형이라는 것, 특정 순서대로 요소를 찾는 것 정도이다.
n이 주어질 때 1부터 n까지의 풍선이 원형으로 놓여있고, 각각 특정 순서를 적어놓은 종이가 들어있다.
맨 처음 순서가 1인 종이를 터뜨려 안의 종이에 적힌 순서의 풍선을 터뜨리고, 마찬가지로 나온 종이에 적힌 순서의 풍선을 터뜨리고… 이를 반복하는 문제이다.
처음 이 문제를 접했을 때는 단순히 요세푸스 문제의 확장 버전이라고 생각하여 해당 알고리즘을 그대로 대입하고 양수일 때, 음수일 때를 가정해서 풀었다.
그런데 이 풀이법에는 문제가 있는데, 풍선들은 고정되어야 한다는 것과 1번 풍선은 항상 가장 먼저 터진다는 것이다.
다시 말해, 기준은 항상 일정하며 1로 시작해야한다.
이를 해결하기 위해 배열을 하나 선언했다. 이 배열은 풍선의 번호와 안에 담긴 다음 순서를 한 번에 담아준다.
1
2
3
4
5
6
7
8
Deque<int[]> q = new ArrayDeque<>();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i < n; i++) {
q.add(new int[]{(i+1), arr[i]});
}
원형을 표현하여 우측, 또는 좌측으로 이동할 수 있어야하기 때문에 Deque를 선언한다. 이때 Deque가 참조하는 타입은 정수형 배열이다.
우선 정수형 배열에 n 다음으로 입력 받는 순서 x를 순서대로 저장하고, q에는 해당 순서를 가진 풍선을 번호에 맞게 저장해준다.
1
2
3
for (int i = 1; i < n; i++) {
q.add(new int[]{(i+1), arr[i]});
}
이제 q의 안에는 { 풍선, 풍선 속의 다음 순서 }가 저장된다.
다음으로 빠른 출력을 위해 StringBuilder를 사용했으며, 이 sb에는 1을 가장 먼저 저장한다.
이는, 가장 먼저 터지는 풍선은 1이기 때문이다.
그 다음 큐 안의 모든 배열을 탐색하여 다음으로 터진 풍선과 그 다음 순서를 원형으로 돌린다. 단, 반복문을 실행하기 위해 초기값을 먼저 할당해주어야 한다.
이 초기값은 1번 풍선이 가진 다음 순서이며 index라는 정수형 변수에 할당해 주었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
StringBuilder sb = new StringBuilder();
sb.append(1).append(' ');
int index = arr[0];
while (!q.isEmpty()) {
if (index > 0) {
for (int i = 1; i < index; i++) {
q.offer(q.poll());
}
int[] next = q.poll();
index = next[1];
sb.append(next[0]).append(' ');
} else {
for (int i = 1; i < -index; i++) {
q.offerFirst(q.pollLast());
}
int[] next = q.pollLast();
index = next[1];
sb.append(next[0]).append(' ');
}
}
while 문 내부를 보면 조건이 분기되어 있다.
이는 양수일 때는 오른쪽으로, 음수일 때는 왼쪽으로 돌아가며 탐색해야하기 때문이다.
다음 순서가 양수인 경우,
반복문을 실행해 1을 제외하고 해당 순서까지 q의 앞 요소를 poll 하고 가장 뒤로 보낸다.
다음으로 반복문을 빠져나오게 되면 터뜨려야하는 풍선에 도달한 것이므로 해당 순서의 q 요소를 빼낸다.
이때, 요소는 { 풍선 번호, 다음 순서 } 형식으로 저장되어 있기 때문에 또다른 배열을 선언하여 해당 배열에 할당한다.
이 배열은 next라 명명했다.
이 next 배열의 0번 인덱스의 값은 현재 터뜨린 풍선의 번호이고, 1번 인덱스의 값은 다음 순서이다.
마찬가지로 음수 역시 같은 로직이다.
다만, 음수의 경우 다음 index가 양수로 치환되어야하기 때문에 반복문 내부에서 양수로 변환해준다.
또 주의해야할 점은 음수인 경우 원에서 좌측으로, 뒤로 이동해야하기 때문에 양수의 방향과 반대로 구현해주어야 한다.
그렇기 때문에 음수인 경우는 큐의 뒷 요소를 맨 앞으로 보내는 것이다.
또한 반복문을 탈출하면 가장 뒤에 있는 요소가 도달한 풍선이기 때문에 next 변수에는 큐의 마지막 요소를 poll 한다.
이를 큐가 빌 때까지 반복하면 정답이 된다.
전체 소스 코드는 다음과 같다.
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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
Deque<int[]> q = new ArrayDeque<>();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i < n; i++) {
q.add(new int[]{(i+1), arr[i]});
}
StringBuilder sb = new StringBuilder();
sb.append(1).append(' ');
int index = arr[0];
while (!q.isEmpty()) {
if (index > 0) {
for (int i = 1; i < index; i++) {
q.offer(q.poll());
}
int[] next = q.poll();
index = next[1];
sb.append(next[0]).append(' ');
} else {
for (int i = 1; i < -index; i++) {
q.offerFirst(q.pollLast());
}
int[] next = q.pollLast();
index = next[1];
sb.append(next[0]).append(' ');
}
}
System.out.println(sb);
}
}
이 문제를 푸느라 시간이 엄청 오래걸렸다.
문제가 어려웠다기 보다는 이전에 풀었던 요세푸스 문제를 대입해서 비슷한 방식으로, 다시 말해 따로 순서를 저장하는 자료구조 없이 진행해보려고 하다가 시간을 많이 잡아먹혔다.
자꾸 될거 같은데 될거 같은데 하다가 결국 해결 못 해서 배열을 사용하게 되었다.
순서가 따로 지정되어 있어서 헷갈렸기도 했는데, 겨우 풀어냈다.
항상 알고리즘 문제를 풀다보면 어떤 문제를 접하던 새롭지만 그 만큼 알게 되는 것도 많아 똑같은 문제를 접했을 때의 대처를 더 잘할 수 있게 된거 같다.