[2346] 풍선 터뜨리기 in python

 > 자료구조

> 덱

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

2346번: 풍선 터뜨리기

 

 

처음 떠올렸던 생각은

array의 값을 하나씩 지워주면

이미 터뜨린 풍선을 따로 뛰어넘는 로직을

만들어줄 필요가 없을 것 같았다.

 

그래서 풍선을 터뜨리는 순간

해당 풍선은 배열에서 값이 사라지게끔 했는데

 

이렇게 하니까

인덱스 번호를 어떻게 남겨야할지 고민이었다.

 

연산으로 할 수 있는지

이것저것 갖다 붙여봤는데

도저히 안돼서

결국,, 인덱스 리스트를 하나 새로 만들어주기로 결정했다

(->구글링을 통해 얻은 해법)

 

왜 인덱스 리스트를 만들어줘야하는지에 대해 생각해봤다.

array에서 풍선을 하나씩 빼오게되면

해당 풍선의 원래의 위치는 없어진다.

하지만 우리는 원래 있던 위치를 출력해줘야 한다.

 

따라서 인덱스 리스트를 통해서

array의 값이 처음에 몇 번째의 위치에 있었는지를

알 수 있다!!!

 

왜 이 생각을 떠올리지 못했을까..

그냥 무작정 연산으로 어떻게든 만들어내야겠다는 생각 뿐이었는데

원래 있던 위치의 인덱스를 구하는 방법에 대해 하나 더 배울 수 있었다.

 

 

그리고 % 연산자에 대해 살짝 헷갈렸던 부분

예를 들어 array[-2 % 4] 이면

array[-2]가 되는 줄 알았는데

인덱스 오류 발생 +_+ !

 

-2 % 4 = -2가 아니라

2였다 띠용!

 

어떻게 구하냐면

(-2 + 4) % 4 = 2 % 4 = 2

% 연산자 오른쪽에 있는 숫자를 왼쪽편에 더해주면 된다...

우씨 나 왜 여태까지 이렇게 알고 있었던 것지 모르겠다 ^^

 

 

 

 

n = int(input())
array = list(map(int, input().split()))
idx = 0
balloon = array.pop(idx)  # 1번 풍선
answer = [1]
idx_list = [i for i in range(2, n + 1)]

for i in range(n-1):
    if balloon<0:
        idx=(idx+balloon)%len(array)
    else:
        idx=(idx+balloon-1)%len(array)
    print(idx+balloon%len(array))
    balloon=array.pop(idx)
    answer.append(idx_list.pop(idx))

print(*answer)

---

2번째 방법!

deque, rotate를 이용해서 구하는 방법!!

https://leonkong.cc/posts/python-deque.html

Python - 데크(deque) 언제, 왜 사용해야 하는가?

 

덱을 이용하여 하게 되면 아래와 같다

from collections import deque

n = int(input())
array =deque(enumerate(map(int, input().split())))
answer=[]

while array:
    idx,balloon=array.popleft()
    answer.append(idx+1)
    if balloon>0:
        array.rotate(-(balloon-1))
    else:
        array.rotate(-balloon)
print(*answer)

 

 

 

여기서 풍선 안에 있는 숫자가 양수일 경우 

-(balloon-1)만큼 회전해준다.

 

[3,2,1,-3,-1]이라는 배열이 있다.

현재 기준점은 idx = 0

오른쪽으로 3칸 이동시키면 우리가 원하는 값은 -3이다. (idx=3)

따라서 0번째 위치에 -3이라는 값이 오게끔 해야 한다는 소리다.

 

따라서 회전을 2번 해주면

[-3,-1,3,2,1]이 되니까

우리가 원하는 값이 0번째 위치에 오게 된다.

 

 

반대로 풍선 안에 있는 숫자가 음수일 경우

-balloon만큼 회전해준다.

 

[-3,-2,-1,3,1]이라는 배열이 있다.

똑같이 기준점은 0번째 위치

왼쪽으로 3칸을 이동시키면 우리가 원하는 값은 -1이다. (idx=3)

-balloon만큼 회전시켜주면 배열은 아래와 같다.

[-1,3,1,-3,-2]