[BOJ 2346] 풍선 터뜨리기

문제 요약

문제 요약
1번부터 N번까지 N개의 풍선이 원형으로 놓여있다.
1번 풍선부터 적혀있는 수대로 이동하여 순차적으로 풍선을 터뜨린다.
단, 터진풍선은 순서에서 제외된다.
양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다.
입력
N (1 <= N <= 1000)
풍선에 적혀있는 수 N개
출력
터진 풍선들의 번호를 차례로 나열

풀이

덱을 이용해 원형으로 놓여져있는 풍선을 구현하여 조사하는 풍선의 수에 맞게 pop과 push를 반복하여 풍선들 사이를 이동하도록 한다.
예를 들어 1번 풍선에 3이 적혀있었다면 확인 후

1. 1번 풍선을 pop한다.
2. 왼쪽pop, 오른쪽push를 2번 반복한다.
3. 다시 왼쪽pop 한다.

이런식으로 1번 풍선의 3칸 오른쪽에 있는 풍선을 pop하도록 한다.

이런식으로 적혀있는 위치의 풍선을 계속 pop하면서 위치를 저장한 뒤 최종적으로 출력하면 풀 수 있다.

덱은 어떻게 구현할까?

큐와 비슷하지만 앞 뒤 모두 pop과 push가 가능하다는 점에서 다른 자료구조이다.
큐처럼 기본적인 함수를 구현한 뒤 추가적으로 pop과 push를 양방향으로 설계해주면 된다.

class deque:
    def __init__(self):
        self.top = []
    def put_front(self, n):
        self.top.insert(0,n)
    def put_behind(self, n):
        self.top.append(n)
    def pop_front(self):
        if not self.isEmpty():
            front = self.top[0]
            del self.top[0]
            return front
        else:
            return -1
    def pop_behind(self):
        if not self.isEmpty():
            return self.top.pop()
        else:
            return -1
    def length(self):
        return len(self.top)
    def isEmpty(self):
        if self.length() == 0:
            return 1
        else:
            return 0
    def isTop(self):
        if not self.isEmpty():
            return self.top[self.length()-1]
        else:
            return -1

주의해야 할 점

풍선의 순서와 가지고 있는 수 모두 저장해야하므로 덱에는 [순서, 수]와 같이 배열을 저장해야 한다.
위와 같이 저장했을 때 가지고 있는 수를 저장하는 임시 변수는 배열을 저장하고 수를 꺼낼 땐 [1]과 같이 인덱싱을 통해 꺼내쓴다.

결과 코드

import sys, queue
input = sys.stdin.readline

N = int(input())
L = list(map(int,input().split()))
result = []

class deque:
    def __init__(self):
        self.top = []
    def put_front(self, n):
        self.top.insert(0,n)
    def put_behind(self, n):
        self.top.append(n)
    def pop_front(self):
        if not self.isEmpty():
            front = self.top[0]
            del self.top[0]
            return front
        else:
            return -1
    def pop_behind(self):
        if not self.isEmpty():
            return self.top.pop()
        else:
            return -1
    def length(self):
        return len(self.top)
    def isEmpty(self):
        if self.length() == 0:
            return 1
        else:
            return 0
    def isTop(self):
        if not self.isEmpty():
            return self.top[self.length()-1]
        else:
            return -1

d = deque()

# 덱 초기화
for i in range(len(L)):
    d.put_behind([i+1, L[i]])

# 첫 번째 풍선의 수를 저장하고 터뜨린다
num = d.pop_front()
result.append(num[0])

# 배열이 텅 빌 때까지 풍선을 터뜨린다
while not d.isEmpty():
	# 양수일 경우
    if num[1] >= 0:
        for _ in range(num[1]-1):
            d.put_behind(d.pop_front())
        num = d.pop_front()
    # 음수일 경우
    else:
        for _ in range(abs(num[1]) - 1):
            d.put_front(d.pop_behind())
        num = d.pop_behind()
    # 꺼낸 수의 순서를 result 배열에 저장
    result.append(num[0])

# 정답 출력
for i in result:
    print(i, end=' ')