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

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

 

 

사용 알고리즘: 덱

 

 

입력

• 첫째 줄에 자연수 N (1 <= N <= 1,000)
• 둘째 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어짐 (종이에 0은 적혀있지 않음)

 

구현 로직

1. 가장 먼저 1번 풍선을 터트려서 종이에 적힌 숫자 만큼 이동

2. 도착한 곳의 풍선을 터트려 종이에 적힌 숫자만큼 이동

3. 풍선이 다 터질 때까지 2를 반복

 

 

아래 그림처럼 원형으로 놓인 풍선을 일자로 핀다고 생각하면 된다.

나는 덱의 0번째 인덱스를 기준점으로 잡고 숫자를 돌리다가 이 자리에 온 숫자를 pop 할 것이다. 

 

 

풍선 안에 적힌 종이에는 0을 제외하고 -N 이상 N 이하의 정수가 적혀있는데, 도는 방향이 다르기 때문에 음수와 양수일 경우를 나눠서 처리해야 한다. 

 

- 음수일 경우

 

기준점을 i 라고 생각했을 때 i-1 이 기준점으로 와야하므로 덱의 오른쪽 끝에 있는 숫자를 제거하고 그 수를 다시 덱의 왼쪽 끝에 추가한다.

( pop -> appendleft )

 

 

- 양수일 경우

 

기준점을 i 라고 생각했을 때 i+1 이 기준점으로 와야하므로 덱의 왼쪽 끝에 있는 수를 제거하고 그 수를 다시 덱의 오른쪽 끝에 추가한다.

( popleft -> append )

 

 

 

그럼 이제 구현한 코드를 살펴보자.

 

덱을 만들고, 덱에 차례로 풍선의 번호를 넣는다. 

 

for 문을 돌면서 기준점(덱의 왼쪽끝)에 와있는 숫자를 pop 해준다 -> 풍선 제거

제거한 풍선 안 종이에 적혀있는 숫자만큼 for 문을 돌면서 숫자를 이동시켜준다. 

 

i = N-1, 즉 마지막 턴이 되면 덱에 1개의 숫자가 남아있고 그 숫자는 기준점에 있기 때문에 위에서 제거된다. 

그 상태로 밑으로 내려가면 인덱스 에러가 나기 때문에 if 문을 통해 len(d) == 0 인 상황을 걸러줘야 한다.

d = deque()
for i in range(N): # 덱에 차례로 풍선 번호를 넣음
    d.append(i)

for i in range(N):
    out = d.popleft() # 풍선 제거
    print(out+1, end=' ') # 풍선 번호 출력
    if len(d) == 0: # 덱에 든게 없으면 break
        break
    rotation = arr[out] # 풍선 안 종이에 적힌 숫자
    if rotation < 0: # 음수일 경우
        for j in range(abs(rotation)): # 종이에 적힌 숫자는 음수일수도 있으므로 절댓값
            x = d.pop() # 제거 
            d.appendleft(x) # 추가
    elif rotation > 0: # 양수일 경우
        for j in range(abs(rotation)-1): # 종이에 적힌 숫자는 음수일수도 있으므로 절댓값
            x = d.popleft() # 제거
            d.append(x) # 추가

 

 

그리고 또 하나 주의해야 할 점은 종이에 적힌 수가 양수일 경우이다.

 

양수일 경우에는 종이에 적힌 수보다 for 문을 1 회 덜 돌도록 코드가 짜여있는데, 아래의 이유 때문이다.

덱의 가장 왼쪽 숫자가 제거되면 숫자들이 자리를 채우기 위해 왼쪽으로 한 칸씩 이동해 자리를 채운다 -> 자동으로 자리가 한 칸 이동된 셈

그래서 양수일 경우에 for 문을 도는 횟수는 abs(rotation)-1 회이다.

 

 

 

전체 코드

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

# 입력
N = int(input())
arr = list(map(int, input().split()))

d = deque()
for i in range(N): # 덱에 차례로 풍선 번호를 넣음
    d.append(i)

for i in range(N):
    out = d.popleft() # 풍선 제거
    print(out+1, end=' ') # 풍선 번호 출력
    if len(d) == 0: # 덱에 든게 없으면 break
        break
    rotation = arr[out] # 풍선 안 종이에 적힌 숫자
    if rotation < 0: # 음수일 경우
        for j in range(abs(rotation)): # 종이에 적힌 숫자는 음수일수도 있으므로 절댓값
            x = d.pop() # 제거 
            d.appendleft(x) # 추가
    elif rotation > 0: # 양수일 경우
        for j in range(abs(rotation)-1): # 종이에 적힌 숫자는 음수일수도 있으므로 절댓값
            x = d.popleft() # 제거
            d.append(x) # 추가

 

 

 

시간 복잡도

 

- 입력

N = int(input())
arr = list(map(int, input().split()))

# O(n)

 

- 덱에 풍선 집어넣는 부분

d = deque()
for i in range(N):
    d.append(i)

# O(n)

 

- 숫자 이동시키는 부분

 

연산

• pop / popleft / append / appendleft: 모두 O(1)

popleft 를 해서 숫자들이 한 칸씩 왼쪽으로 이동했는데 왜 O(1) 시간이지? 라는 의문이 들 수 있다. 

 

궁금해서 찾아보았다!

리스트의 경우 맨 앞의 숫자가 제거되면 O(n) 시간이 맞지만, deque 는 이중 연결 리스트와 비슷한 구조를 가지고 있어 추가와 삭제 연산이 효율적이라고 한다. 그래서 popleft 를 해도 O(1) 시간밖에 안 걸린다!

for i in range(N):
    out = d.popleft()
    print(out+1, end=' ')
    if len(d) == 0:
        break
    rotation = arr[out]
    if rotation < 0:
        for j in range(abs(rotation)):
            x = d.pop()
            d.appendleft(x)
    elif rotation > 0:
        for j in range(abs(rotation)-1):
            x = d.popleft()
            d.append(x)
            
# O(n^2)

 

 

그래서 총 시간 복잡도를 구해보면, O(n^2) 의 시간 복잡도를 가지는 것을 알 수 있다.

- 입력: O(n)

- 덱에 풍선 집어넣는 부분: O(n)

- 숫자 이동시키는 부분: O(n^2)