백준 1021번: 회전하는 큐 (파이썬)

자료구조를 활용하는 문제

파이썬에는 deque라고 하는 양쪽으로 데이터를 넣고 뺄 수 있는 자료구조가 존재하는데 이걸로 양방향 순환 큐를 구현했다.

 

from collections import deque

n, m = map(int, input().split())
m_list = list(map(int, input().split()))

# 회전하는 큐 생성
n_list = deque(i+1 for i in range(n))

cnt = 0
for i in range(m):
  while(True):
    # 첫번째 자리에 원하는 수가 나올때까지 회전을 반복
    if m_list[i] == n_list[0]:
      n_list.popleft()
      break
    else:
      # 리스트의 길이를 2로 나눈 값으로 앞에 있는지 뒤에 있는지 구분
      if n_list.index(m_list[i]) > (len(n_list) // 2):
        # .rotate(양수)면 수만큼 오른쪽으로 회전
        n_list.rotate(1)
        cnt += 1
      else:
        # .rotate(음수)면 수만큼 왼쪽으로 회전
        n_list.rotate(-1)
        cnt += 1
  
print(cnt)

 

처음에 실행하는데 계속 숫자가 애매하게 틀리는 것 같아 왜그런가 했더니

첫번째 자리에 왔을 때만 뽑아야 하는데 맨뒤에 도착해도 뽑아버린 사람 나야나