풍선 터뜨리기
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번 풍선의 순서대로 터지게 된다.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 종이에 0은 적혀있지 않다.
출력
첫째 줄에 터진 풍선의 번호를 차례로 나열한다.
문제 풀이 방법 및 해설
이번 문제는 단순 자료구조 문제이다. 풍선에서 나온 값에 따라 마지막 데이터를 제거하고 처음에 추가하거나 처음 데이터를 제거하고 마지막 데이터에 추가하면 된다.
만약 풍선에 적힌 값이 양수라면 처음 데이터를 제거하고 마지막에 추가하고 음수라면 마지막 데이터를 제거하고 처음에 추가하면 된다. 여기서 주의할 점은 양수인 경우 풍선이 터지면서 자연스럽게 위 과정을 거치므로 값에서 1을 빼서 진행을 하면 된다!
예시를 들어 2 3 1 2 4일 경우 2가 터지면 다음에 숫자는 2를 기준으로 오른쪽 두 칸을 이동한 1이 되어야 하는데 2가 터짐과 동시에 3 1 2 4에 기준이 3으로 바뀌므로 1을 뺀 값을 옮기면 된다.
여기까지 풀이했을 때 무조건 정답이라고 생각했지만 메모리초과라는 오류를 받게되었다. 이에 대해서 학습을 해본 결과 Deque의 구현체로는 LinkedList와 ArrayDeque가 있는 것을 알게 되었다. 그리고 알게된 2개의 차이점을 설명해보겠다.
- ArrayDeque은 LinkedList와 달리 다음 노드에 대한 참조를 유지할 필요가 없기 때문에 더 적은 메모리를 사용한다.
- ArrayDeque은 LinkedList보다 cache-locality에 좀 더 친숙하다.
- ArrayDeque의 내부 배열이 가득 차면 크기를 두 배로 늘리고 모든 데이터를 복사해야 하기 때문에 시간이 조금 더 걸린다.
풀이 코드
import java.io.*;
import java.util.*;
import java.util.LinkedList;
public class Main {
public static class Node{
int idx, value;
public Node(int idx, int value) {
this.idx = idx;
this.value = value;
}
}
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());
Deque<Node> dq = new ArrayDeque<>();
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 1 ; i <= N ; i++){
int value = Integer.parseInt(st.nextToken());
dq.offer(new Node(i, value));
}
while(dq.size() > 1){
Node node = dq.poll();
int idx = node.idx;
int value = node.value;
if(value > 0 ){
value--;
for(int i = 0 ; i < value ; i++){
dq.offer(dq.poll());
}
}else{
value = Math.abs(value);
for(int i = 0 ; i < value ; i++){
dq.offerFirst(dq.pollLast());
}
}
sb.append(idx + " ");
}
sb.append(dq.poll().idx);
System.out.println(sb);
}
}
