백준 2346) 풍선 터뜨리기 (Deque)

https://www.acmicpc.net/problem/2346

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은 적혀있지 않다.

출력

첫째 줄에 터진 풍선의 번호를 차례로 나열한다.

 

---

 

접근 방법

 

본 문제는 ArrayList 등으로 배열 접근 방식을 사용할 수 있지만,

알고리즘 분류가 Deque로 설정돼있어서 이를 적용시켜봤다.

 

Key Point

 

• 풍선 안의 종이가 양수일 때는 오른쪽으로
• 풍선 안의 종이가 음수일 때는 왼쪽으로

 

1. 양수일 때 오른쪽으로

 

문제 예시

 

 

첫 번째 풍선을 터뜨리면 우측으로 3칸 이동해야 한다.

3칸 이동하면 -3 종이를 가진 풍선에 도달해야 하는데,

첫 번째 풍선을 pollFirst 한 후에 두 번째, 세 번째 (3 - 1 = 2번)를 오른쪽으로 붙어야 -3 종이를 가진 풍선이 다시 맨 앞으로 올 수 있다.

 

 

여기서 알 수 있는 것은 양수가 담긴 풍선을 터뜨리면 다음 터뜨릴 풍선이 맨 처음에 온다.

 

 

 

2. 음수일 때 왼쪽으로

 

다음 예시

 

 

-3 종이가 담긴 풍선을 터뜨리면 좌측으로 3번 이동해야 한다.

이는 맨 뒤의 원소를 맨 앞으로 붙이는 것과 같은데, 양수일 때 오른쪽으로 이동할 때와 마찬가지로 (|-3| -1 = 2번)을 붙어야 한다.

 

 

여기서 알 수 있는 것은 음수가 담긴 풍선을 터뜨리면 다음 터뜨릴 풍선이 맨 끝에 온다.

 

 

이전에 터뜨린 풍선이 양수인지 음수인지 구분하기 위해 prev 변수를 설정해서

prev에 저장된 값이 양수라면 맨 앞 원소를 추출하고, 음수라면 맨 뒤 원소를 추출하면 된다.

 

int prev = 0;

while(..) {
Balloon cur = (prev >= 0) ?deque.pollFirst() : deque.pollLast();

....

prev = cur.element;

}

 

 

 

 

if(cur.element > 0) {
	deque.addLast(deque.pollFirst());
}

 

만약 원소가 하나 있다면 어떻게 될까?

원소를 하나 뽑게 되면 덱에 남아있는 원소가 없게 되므로 addLast 에 NullPointerException 예외가 발생한다.

 

NullPointerException 예외 발생

 

 

 

소스 코드

 

import java.util.*;

class Main {
    static class Balloon {
        int idx;
        int element;

        public Balloon(int idx, int element) {
            this.idx = idx;
            this.element = element;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Deque<Balloon> deque = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            deque.add(new Balloon(i, sc.nextInt()));
        }

        int prev = 0;
        StringBuilder ans = new StringBuilder();

        while (deque.size() > 1) {
            Balloon cur = (prev >= 0) ?deque.pollFirst() : deque.pollLast();
            for (int i = 0; i < Math.abs(cur.element)-1; i++) {
                if(cur.element > 0)
                    deque.addLast(deque.pollFirst());
                else
                    deque.addFirst(deque.pollLast());
            }

            prev = cur.element;
            ans.append(cur.idx).append(" ");
        }
        ans.append(deque.poll().idx);

        System.out.println(ans);
    }
}