[백준/Python] 1021번 - 회전하는 큐

문제

1021번 - 회전하는 큐

해결과정

• rotate 몰랐으면 오래걸렸을 듯..
• i가 m이랑 다르다면 while문을 돈다.
  • 큐 맨 앞 값이 찾는 위치라면 pop
  • 아니라면 오른쪽으로 회전할지, 왼쪽으로 회전할지 확인한다.
    • 둘 중 가장 최소로 회전하는 쪽으로 회전
    • 회전 횟수만큼 cnt에 더 해준다.

덱 문법

• deque은 스택과 큐의 기능을 가진 객체로 출입구를 양쪽으로 가지고 있음
• 스택처럼 써도 되고, 큐처럼 써도 됨

# 먼저 deque를 만들자
from collections import deque
dq = deque('python')
print(dq)         # deque(['p', 'y', 't', 'h', 'o', 'n'])

# 1. 스택 구현: append, pop
# 오른쪽 끝에 추가
dq.append('x')  
print(dq)          # deque(['p', 'y', 't', 'h', 'o', 'n', 'x'])

# 오른쪽 끝에 가져오면서 삭제
print(dq.pop())    # x
print(dq)          # deque(['p', 'y', 't', 'h', 'o', 'n'])

# 2. 큐 구현: appendleft, pop, append, popleft
# 오른쪽 왼쪽 추가
dq.appendleft('A')  
print(dq)          # deque(['A', 'p', 'y', 't', 'h', 'o', 'n'])

# 왼쪽 끝에 가져오면서 삭제
print(dq.popleft())    # A
print(dq)          # deque(['p', 'y', 't', 'h', 'o', 'n'])

# 3. deque 확장: extend, extendleft
dq.extend('TEST')
print(dq)          # deque(['p', 'y', 't', 'h', 'o', 'n', 'T', 'E', 'S', 'T'])

dq.extendleft('coding')   
print(dq)          # deque(['g', 'n', 'i', 'd', 'o', 'c', 'p', 'y', 't', 'h', 'o', 'n', 'T', 'E', 'S', 'T'])

# 4. 리스트처럼 사용: insert, remove
dq = deque('Good')
dq.insert(4,'s')
print(dq)          # deque(['G', 'o', 'o', 'd', 's'])

# 왼쪽부터 삭제 됨
dq.remove('s')
print(dq)          # deque(['G', 'o', 'o', 'd'])

# 5. 좌우반전: reverse
dq.reverse()       # deque(['d', 'o', 'o', 'G'])
print(dq)

# 6. 회전
dq = deque([1,2,3,4,5])

# 양수는 오른쪽으로 회전
dq.rotate(2)
print(list(dq))    # [4, 5, 1, 2, 3]

# 음수는 왼쪽으로 회전
dq.rotate(-2)
print(list(dq))    # [3, 4, 5, 1, 2]

풀이

from collections import deque
import sys

n,m = map(int, sys.stdin.readline().split())

# 뽑아내려고 하는 숫자들의 위치
position = list(map(int,sys.stdin.readline().split()))

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

# 연산 횟수
cnt = 0

i = 0
while i != m:
  if q[0] == position[i]:
    q.popleft()
    i += 1
  else:
    Rlen = len(q) - q.index(position[i])
    Llen = q.index(position[i])
    if Rlen > Llen:
      q.rotate(-Llen)
      cnt += Llen
      q = q
    else:
      q.rotate(Rlen)
      cnt += Rlen
      q = q

print(cnt)