[Python] BOJ 2346 - 풍선 터뜨리기

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

2346번: 풍선 터뜨리기

# deque를 사용해서 풀어야 하는 문제이다.

 

1. 풍선안에 있는 숫자들을 s로 입력받고 인덱스와 함께 dq에 저장한다.

    s = [3, 2, 1, -3, -1]이면, dq = [[1, 3], [2, 2], [3, 1], [4, -3], [5, -1]]이 된다.

 

2. dq에 원소가 존재하는 동안 반복문을 돌며

   dq의 첫번째 원소를 pop해서 answer에 index를 넣어준다.

   dq의 하나의 원소만 남았다면, 그 원소의 인덱스를 answer에 넣어주고

   2개 이상의 원소가 존재한다면, move(풍선에 써 있는 움직여야하는 숫자)를 확인한다.

 

3. move가 양수이면, 오른쪽으로 이동해야 한다. 

   오른쪽으로 이동한다는 것은 '커서'를 오른쪽으로 한칸 이동 하는 방법이 대부분 떠오르겠지만, 

   커서를 맨 앞에 고정시켜놓고 원소들을 이동하는 방법도 있다.

 

 # 즉, 오른쪽으로 한칸 이동하는 것은 커서를 맨 앞으로 고정시켜놓았을 때,

   맨 앞의 원소를 pop해서 맨 뒤에 append하면 자동으로 2번째 원소가 맨 앞으로 오면서

   커서가 2번째 원소를 가리키게 된다.

 

 # 반대로, 왼쪽으로 한 칸 이동하는 것은 커서를 맨 앞으로 고정시켜놓았을 때,

   맨 뒤의 원소를 pop해서 맨 앞에 append하면 맨 앞에 마지막원소가 오면서

   커서가 마지막 원소를 가리키게 된다.

 

   따라서, move가 양수이면 move - 1만큼 dq.popleft()한 뒤 dq.append()해준다.

   반대로 move가 음수이면 abs(move)만큼 dq.pop()한 뒤 dq.appendleft()해준다.

 

 

# 처음에 deque.rotate(move)를 하려 했는데, 이건 O(N)이라

   N이 1000이 들어오면 계속 몇백번의 이동을 해야 해서 시간 초과가 날 것이라 생각했다.

   따라서, deque의 appendleft와 popleft를 적절히 이용해서 O(1)에 풀이를 했다.

 

# deque에서는 맨 앞의 원소를 pop하는 popleft()와 맨 뒤에 원소를 pop하는 pop(), 

                           맨 앞에 원소를 추가하는 appendleft()와 맨 뒤에 원소를 추가하는 append() 

                           연산이 모두 O(1)이다.

  

from collections import deque
N = int(input())
s = list(map(int,input().split()))
dq = deque()
for idx, num in enumerate(s, 1):
	dq.append([idx, num])
answer = []
while dq:
	idx, move = dq.popleft()
	answer.append(idx)
	if len(dq) == 1:
		answer.append(dq.pop()[0])
	else:
		if move > 0 :
			for _ in range(move - 1):
				dq.append(dq.popleft())
		else:
			for _ in range(abs(move)):
				dq.appendleft(dq.pop())

print(*answer)

(solved.ac 티어: 실버 3)