[파이썬] [2346 - 풍선 터트리기]

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

2346번: 풍선 터뜨리기

[나의 문제 분석]

요세푸스 문제(https://jobdong7757.tistory.com/113?category=916339)와 비슷했던것 같다. 근데 문제는 여기서 s 배열에 음수가 존재하면 오른쪽이 아닌 왼쪽으로 원을 둘러서 가야된다는 사실이다. 이 부분때문에 헷갈려서 헤매었다. 그리고 처음 시작점이 여기서는 0으로 지정되어있다. 그래서 한번 삭제를 하고 반복문을 돌려주어야 한다. 

[나의 해결 방안]

n=int(input())
s=list(map(int,input().split()))
start=0
index=[x for x in range(1,n+1)]
answer=[]
temp = s.pop(start)
answer.append(index.pop(start))

while s:
    if temp<0:
        start = (start+temp)%len(s)
    else:
        start=(start+temp-1)%len(s)
    temp = s.pop(start)
    answer.append(index.pop(start))
for i in answer:
    print(i,end=' ')

 

n과 s는 주어진 입력이고 start에는 다음 지점을 저장해주려고 하였다. index는 정답에 저장하기 위해서(정답은 0 index를 1로 바꿔서 출력해주어야하기 때문)에 사용하였다. temp에는 s배열의 값을 temp에 저장해주었다.

while문을 하기 전에 이 문제는 시작점이 0으로 정해져있기 때문에 start=0으로 초기화 하고 temp는 s의 start값의 index를 pop해서 저장해준다. 

while문을 이제 시작할때 temp의 값이 음수일때가 문제인데 이 문제를 python의 나머지 기호(%)를 잘몰랐던 나의 무지였었다. 

https://seokdev.site/204 이 사이트에서 다시 공부하고 왔다.. python에서는 c언어의 %와 달리 -1%10을 하면 9가 나오게 된다. 즉, A%B 가 있으면, A에다가 B를 계속 더하면서 처음으로 양수가 되었을 때 B로 나눠 나머지를 준다.

예를 들어 -1%10이면 -1+10=9, 9%10=9 이런식으로 나오는 것이다.

이 문제에서 temp가 음수이면 그냥 start에 temp를 더해서 s의 길이로 나누면 왼쪽으로 -temp만큼 가는것처럼 보이게 되는 것이다. 그래서 temp<0일 때를 처리해 줄 수 있다.

[다른 사람 풀이]

위의 풀이가 temp<0을 처리하기 제일 용이했었는데 그것 말고도 deque에 temp<0을 처리해줄 수 있는 방법도 있었다.

 

enumerate는 반복문 사용 시 몇 번째 반복문인지 확인이 필요할 때 사용할 수 있다. 이거는 index 번호와 collection의 원소를 tuple 형태로 반환한다. 

예를 들어 이런식이다.

t = [1, 5, 7, 33, 39, 52]
for p in enumerate(t):
	print(p)

(0, 1)
(1, 5)
(2, 7)
(3, 33)
(4, 39)
(5, 52)

그리고 deque의 rotate() 메서드.

deque.rotate(num)을 하면 deque를 num만큼 회전한다.(양수면 오른쪽, 음수면 왼쪽)

# Contain 1, 2, 3, 4, 5 in deq
deq = deque([1, 2, 3, 4, 5])

deq.rotate(1)
print(deq)
# deque([5, 1, 2, 3, 4])

deq.rotate(-1)
print(deq)
# deque([1, 2, 3, 4, 5])

그래서 위 문제는 다음과 같이 풀 수 있다. (참고: https://par3k.tistory.com/215)

from collections import deque
n = int(input())
q = deque(enumerate(map(int,input().split())))
ans=[]

while q:
    idx,num = q.popleft()
    ans.append(idx+1)
    if num>0:
        q.rotate(-(num-1))
    elif num<0:
        q.rotate(-num)
print(' '.join(map(str,ans)))

아까처럼 temp>0일때는 rotate를 시계반대방향으로(왼쪽)하면 되니까 q.rotate(-(num-1))을 하였다. num-1을 한것은 해당하는 풍선은 터뜨려야 하기 때문에. 

그리고 num<0이면 q.rotate(-num)을 하면 된다. -num은 양수이므로 오른쪽(시계방향으로) rotate된다.