[백준] 2346 풍선 터뜨리기

문제

www.acmicpc.net/problem/2346

 

 

코드

from collections import deque

N = int(input())
q = deque([(num, idx) for idx, num in enumerate(map(int, input().split()))])
answer = []

while q:
    num, idx = q.popleft()
    answer.append(idx+1)

    if q and num > 0:
        q.rotate(-1 * (num-1))
    elif q and num < 0:
        q.rotate(-1 * num)

print(" ".join(map(str,answer)))

 

풀이

1. 첫번째 숫자는 우선적으로 popleft()를 통해 꺼낸다.

2-1. q에 풍선이 남아있고, num이 양수일 때 -(num-1) 만큼 회전시킨다.

       왜 -1 * (num-1) 인가?

       -1 : rotate 함수는 양수면 오른쪽, 음수면 왼쪽으로 회전시킨다. 풍선을 deque 기준 left에 오게끔 하려면 왼쪽으로 회전시켜야 하므로

       num-1 : q.popleft()를 통해 먼저 풍선을 터뜨렸고, 양수면 왼쪽으로 회전시켜야 하는데 popleft()를 통해 위치 1을 왼쪽으로 옮긴게 된 것이므로 1개 적게 회전.

q = deque([3, 2, 1, -3, -1])
q.rotate(1)
print(q)
# deque([-1, 3, 2, 1, -3])

 

2-2. q에 풍선이 남아있고, num이 음수일 때 -1 * num 만큼 회전시킨다.

       왜 -1 * num 인가?

       -1 : rotate 함수는 양수면 오른쪽, 음수면 왼쪽으로 회전시킨다. 풍선을 deque 기준 left에 오게끔 하려면 오른쪽으로 회전시켜야 하므로

       num : 양수와 반대로 1을 빼지 않는 이유는 오른쪽으로 회전시켜야 하므로 popleft()를 해도 양수처럼 적용되지 않기 때문이다.

 

관련 개념/문법 정리

deque

 

from collections import deque

 

• deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.
• deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.
• deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
• deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
• deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가한다.
• deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가한다.
• deque.remove(item): item을 데크에서 찾아 삭제한다.
• deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).

enumerate

a = ['first','second','third']
b = list(enumerate(randomlist))
c = dict(enumerate(randomlist))

#b [(0, 'first'), (1, 'second'), (2, 'third')]
#c {0: 'first', 1: 'second', 2: 'third'}