[python] 백준 2346 - 풍선 터뜨리기 (원형큐 응용)

1. 문제 설명

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

2346번: 풍선 터뜨리기

 

1-1. 모듈러 연산

≪cf≫ Division Algorithm

: ∀a,b ∈Z, b>0 then ∃! q, r s.t a= b*q +r(0≤r<b) 

: 인덱스를 벗어나는 경우 재설정하는 방법으로 모듈러 연산 적용

: 이때 Ⅱ 경우, 파이썬이기에 a가 음수인 경우에도 모듈러 연산 그대로 적용 가능 

 

1-1-1. Python에서의 모듈러 연산

: Python에서의 음수의 모듈러 연산 방식은 나머지 값이 음수인 경우 x mod y 일때 결과값이 0이상의 정수가 나올때까지 y를 더한다

⇔ 결과가 0 또는 양수로 나옴

e.g. -5 % 4 → (-5) + 4 = -1

                    → (-1) + 4 = 3

 

 

2. 구현

2-1. 리스트 이용

 

2-1-1. 동작과정

 

2-1-2. 사용 함수

: enumerate(iterable, startIndex) (default = 0)

→ 반환값 : iterable 개체에 대한 각 항목에 대한 카운트 값과 함께 반복가능한 개체 반환

 

2-1-3. 구현

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    
    ballons = list(enumerate(list(map(int, input().split())),start=1))
   

    idx=0
    while(ballons):
        value, move = ballons.pop(idx)
        print(value, end=" ")
        if(move>0 and ballons):
            idx= (idx+(move-1))%len(ballons)
            
        elif(move<0 and ballons):
            idx += move
            idx%=len(ballons)
        


if __name__=="__main__":
    main()

 

2-2. 모듈 deque 이용

2-2-1. 동작 과정

≪cf≫

: 이때 0번째 인덱스의 데이터를 pop할 때마다 전체 데이터는 왼쪽으로 1칸씩 회전됨

→ 시계반대로 회전할 경우에는 (move-1)칸만큼 회전해야한다

→ 시계방향으로 회전할 경우에는 어차피 오른쪽으로 회전할 것이기에 영향이 없다

 

2-2-2. 사용 함수

: deque.rotate()

e.g. rotate(-1) / rotate(1) : 원형 큐를 반시계/시계방향으로 1칸 회전시킴

 

       

사진 출처 : https://velog.io/@hygge/Python-%EB%B0%B1%EC%A4%80-2346-%ED%92%8D%EC%84%A0-%ED%84%B0%EB%9C%A8%EB%A6%AC%EA%B8%B0-deque

 

2-2-3. 구현

import sys
from collections import deque
input = sys.stdin.readline

def main():

    N = int(input())
    ballons = deque(enumerate(map(int,input().split()),start=1))

    while(ballons):
        data, move = ballons.popleft()
        print(data, end=" ")
        if(move>0 and ballons):
            ballons.rotate(-(move-1))
        elif(move<0 and ballons):
            ballons.rotate(-move)


if __name__=="__main__":
    main()