[백준/Python] 2346 : 풍선 터뜨리기

 

위 테스트케이스 예시를 단계별로 풀어보면 다음과 같다.

 

# [(0, 3), (1, 2), (2, 1), (3, -3), (4, -1)] : 1
# [(3, -3), (4, -1), (1, 2), (2, 1)] : 4
# [(4, -1), (1, 2), (2, 1)] : 5
# [(2, 1), (1, 2)] : 3
# [(1, 2)] : 2

 

풍선들의 현재 순서 (인덱스) 와 풍선 안에 적혀있는 번호 모두 사용해야 하므로 enumerate를 사용해야 겠다고 판단함.

따라서 위처럼 리스트 내에 각 풍선별로 (인덱스, 숫자) 쌍으로 구성되어 있다.

 

리스트를 큐처럼 사용해볼까 하다가 앞뒤로 이어져 있기도 하고 각 풍선의 숫자만큼 이동한다는 점에서 데크로 사용하는 것이 좋을 듯 싶어서 deque를 호출하였음

 

참고로 deque의 함수를 몇 가지 정리해보면 다음과 같은데, 이 중에서 rotate 함수를 적절히 활용하여 현재의 풍선을 맨 앞으로 (첫 번째 원소로) 이동시키는 구조를 활용해보았다.

 

<deque 속성>

queue = deque(['a', 'b', 'c'])

# 큐의 끝에 삽입
queue.append('k') # ['a', 'b', 'c', 'k']

# 큐의 앞에 삽입
queue.appendleft('m') # ['m', 'a', 'b', 'c', 'k']

# 큐의 끝에서 삭제
queue.pop() # ['m', 'a', 'b', 'c']

# 큐의 앞에서 삭제
queue.popleft() # ['a', 'b', 'c']

# 부호에 따라 왼/오른쪽으로 덱을 이동시킴
queue1.rotate(-1) # ['b', 'c', 'a']
queue2.rotate(1) # ['c', 'a', 'b']

 

 

 

1. 첫 번째 시도

from collections import deque

N = int(input())
balloons = deque(enumerate(map(int, input().split()))) 
answer = []   # 터진 풍선들의 인덱스 번호 리스트

for _ in range(N):
    answer.append(balloons[0][0]+1)
    now = balloons[0][1]
    balloons.popleft()
    if now > 0: balloons.rotate(now-1)
    else: balloons.rotate(now)

print(answer)

 

위 코드는 테스트케이스에서는 올바르게 작동되었지만, 제출했더니 틀렸다고 나온 코드임

보니까 풍선을 회전할 때 조건에서 now 값이 음수일 경우 회전하는 방향은 왼쪽이어야 하는데, now 만큼 정확하게 회전하는 것이 아니라는 점에서 오차가 발생하는 것 같았다.

현재 풍선이 터지고 난 다음에 풍선이 바로 그 자리에 와야 하므로, 이 회전하는 조건을 변경해보았다.

 

 

2. 정답 코드

from collections import deque

N = int(input())
balloons = deque(enumerate(map(int, input().split()))) # [(0, 3), (1, 2), (2, 1), (3, -3), (4, -1)]
answer = []   # 터진 풍선들의 인덱스 번호 리스트

for _ in range(N):
    idx, move = balloons.popleft()
    answer.append(idx+1)
    
    if balloons:
        if move > 0: balloons.rotate(-(move-1))
        else: balloons.rotate(-move)

print(*answer)

 

먼저 deque에서 popleft()를 하여 맨 첫 번째(왼쪽) 요소를 제거함과 동시에, 이것의 인덱스와 숫자를 각각 idx, move 변수에 저장하도록 한다.

그 후 터진 풍선들의 인덱스 리스트인 answer에 idx+1를 저장해주고,

if 문으로 풍선 속 숫자(move)가 양수여서 오른쪽으로 이동할 경우 -(move-1) 로 처리하여 정확한 위치로 이동하도록 하였고, 음수여서 왼쪽으로 이동할 때는 -move로 처리해 풍선의 순서를 적절히 유지하였다.

 

마지막으로 현재 결과를 담고 있는 answer는 리스트 형식이므로, 마지막에 언패킹 연산자인 * 기호를 사용해준다.

이는 리스트나 튜플과 같은 iterable의 요소를 각각의 인수로 나누어 전달하는 역할을 하며, 이를 사용하면 리스트나 튜플을 그대로 출력하지 않고, 각 요소를 공백으로 구분된 형태로 출력할 수 있음!