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번 풍선 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다고한다. 즉, 원형으로 이어져있으므로 이를 해결할 방안을 덱에 추가해주어야할 것 같다.
다음은 연결리스트로 구현한 덱이다. 원형으로 구현하기 위해 첫 번째 노드를 가리키는 firstNode의 previous 노드를 lastNode로 하고, lastNode 또한 lastNode의 nextNode를 firstNode를 가리키게끔 하여 원형으로 구현하였다.
static class CustomLinkedList{
Node firstNode;
Node lastNode;
CustomLinkedList(){
firstNode = null;
lastNode = null;
}
// 노드 add 메서드
public void add( int index, int value ){
Node node = new Node( index, value );
if( firstNode == null ){
firstNode = node;
lastNode = node;
firstNode.nextNode = lastNode;
firstNode.previousNode = lastNode;
}else{
lastNode.nextNode = node;
node.previousNode = lastNode;
node.nextNode = firstNode;
firstNode.previousNode = node;
lastNode = node;
}
}
// moveIndex만큼 왼쪽으로 이동 후
// 해당 노드 반환
public Node left( int moveIndex, Node node ){
while( moveIndex++ != 0 ){
node = node.previousNode;
}
return node;
}
// moveIndex만큼 오른쪽으로 이동 후
// 해당 노드 반환
public Node right( int moveIndex, Node node ){
while( moveIndex-- != 0){
node = node.nextNode;
}
return node;
}
// 노드 삭제
public void delete( Node deleteNode ){
if( deleteNode == firstNode ){
firstNode = firstNode.nextNode;
firstNode.previousNode = lastNode;
lastNode.nextNode = firstNode;
}else if( deleteNode == lastNode ){
lastNode = lastNode.previousNode;
lastNode.nextNode = firstNode;
firstNode.previousNode = lastNode;
}else{
deleteNode.previousNode.nextNode = deleteNode.nextNode;
deleteNode.nextNode.previousNode = deleteNode.previousNode;
}
}
}
static class Node{
int index;
int value;
Node nextNode;
Node previousNode;
Node( int index, int value ){
this.index = index;
this.value = value;
nextNode = null;
previousNode = null;
}
}left 메서드와 right 메서드는 풍선 안 종이에 적혀있는 값만큼 이동하기 위해 작성하였다. 종이에 적혀있는 값이 음수라면 left 메서드를 호출하고 양수라면 right 메서드를 호출한다.
다음은 제출한 풀이 코드이다.
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
CustomLinkedList dequeue = new CustomLinkedList();
for( int i = 1; i <= N; i++ )
dequeue.add( i, Integer.parseInt(st.nextToken()) );
// 첫 번째 풍선먼저 터뜨리므로 node 변수는 첫 번째 노드를 가리킨다.
Node node = dequeue.firstNode;
while( N-- > 0 ){
Node tempNode;
// node를 삭제한다.
dequeue.delete(node);
// 노드의 값이 양수라면
// right 메서드를 호출하고
// tempNode에 해당 노드를 가리키게한다.
if( node.value > 0 )
tempNode = dequeue.right( node.value, node );
// 노드의 값이 음수라면
// left 메서드를 호출하고
// tempNode에 해당 노드를 가리키게 한다.
else
tempNode = dequeue.left( node.value, node );
// 노드의 인덱스를 출력한다.
sb.append(node.index).append(" ");
// node를 tempNode를 가리키게한다.
node = tempNode;
}
System.out.println(sb.toString());
}처음에는 첫 번째 풍선을 터뜨리므로 node 변수에 첫 번째 노드를 가리키게한다. 그리고, node가 가리키고 있는 노드에 대한 정보는 남아있으므로 delete() 메서드를 호출해 node를 삭제한다. 그 후 node 변수를 토대로 좌우 둘 중 한 방향으로 이동하고 tempNode에 반환한다. tempNode는 다음에 터뜨릴 풍선과 동일하므로 node 변수에 저장한다.
나가는 글
큐와 덱을 얼마나 잘 이해하는지 시험해볼 좋은 문제인 것 같다.
스스로 생각하기에 풍선이 원형으로 되어있다는 점에서 첫 번째 노드와 마지막 노드를 연결한 것과 left, right 메서드를 떠올렸다는 점이 나쁘지않았던 것 같다.
