백준 2346_풍선 터뜨리기 / Python

문제

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.

우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.

예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 종이에 0은 적혀있지 않다.

출력

첫째 줄에 터진 풍선의 번호를 차례로 나열한다.

예제 입력 1 

5
3 2 1 -3 -1

예제 출력 1 

1 4 5 3 2

---

import sys
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
sequence = [True for _ in range(n)]

print(1, end=' ')
cur=0  #현재위치
sequence[cur] = False #첫번째 풍선 터지면서 시작
for i in range(n):
  if sum(sequence)==0: #다 터지면 멈춤
    break
  move = nums[cur] #움직여야하는 순서 수
  while move != 0:
    if move > 0: #오른쪽으로
      if cur + 1 == n: #마지막 칸이면 처음칸으로
        cur = 0

      if sequence[cur + 1]==1: # 다음이 안터진 풍선이면 움직여야하는 칸수 -= 1
        move -= 1

      cur += 1 #다음위치로
     
    elif move < 0:
      if cur - 1 == -1:
        cur = n

      if sequence[cur - 1]==1: 
        move+=1
        
      cur -= 1
      
  sequence[cur] = False #move==0일 때 현재 칸 풍선 터뜨리기
  print(cur + 1, end = ' ')

시간이 너무 오래걸림... 왜지

 

import sys
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
sequence = [True for _ in range(n)]

print(1, end=' ')
cur=0  #현재위치
sequence[cur] = False #첫번째 풍선 터지면서 시작

while sum(sequence) != 0:
  move = nums[cur] #움직여야하는 순서 수
  while move != 0:
    if move > 0: #오른쪽으로
      if cur + 1 == n: #마지막 칸이면 처음칸으로
        cur = 0

      if sequence[cur + 1]==1: # 다음이 안터진 풍선이면 움직여야하는 칸수 -= 1
        move -= 1

      cur += 1 #다음위치로
     
    elif move < 0:
      if cur - 1 == -1:
        cur = n

      if sequence[cur - 1]==1: 
        move+=1
        
      cur -= 1
      
  sequence[cur] = False #move==0일 때 현재 칸 풍선 터뜨리기
  print(cur + 1, end = ' ')

9번째 줄에 for 문과 if문이 불필요한거 같아서 while문으로 합쳐줬는데

더 오래걸림..!!ㅜ

 

deque로 풀어볼게요..

deque는 double ended queue. 양쪽 끝에서 삽입과 삭제가 가능한 자료구조.

rotate(n) 함수쓰면 될 듯.

import sys
from collections import deque
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))

a=[i for i in range(2, n+1)]
q=deque(a)

print(1, end = ' ')
cur = 1
for i in range(n-1):
  c= nums[cur-1]
  if c > 0:
    q.rotate(-(c - 1))
  else:
    q.rotate(-c)
  cur = q.popleft()
  print(cur, end=' ')

 

어렵네요.. 

rotate(n)에서 n이 양수이면 시계방향, 음수이면 반시계방향.

c = nums[cur-1]가 양수이면 c - 1만큼 반시계로 회전

c = nums[cur-1]가 음수이면 abs(c)만큼 시계로 회전

그치만 시간은 확실히 줄었다.