[ 백준 ] 1021. 회전하는 큐

문제

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

 

 

 

아이디어

오른쪽, 왼쪽 모두 이동이 가능해야 하고, 맨 앞의 요소를 pop해야 하므로 deque 자료구조 활용

뽑아내야 하는 수의 index를 알아내 회전 방향 결정

 

 

 

풀이

from collections import deque

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

answer = 0
arr = deque(range(1, n + 1))

for pick in pick_list:
    idx = arr.index(pick)
    if idx <= (len(arr) // 2):
        # 왼쪽으로 한 칸 이동
        while arr[0] != pick:
            arr.append(arr.popleft())
            answer += 1
    else:
        # 오른쪽으로 한 칸 이동
        while arr[0] != pick:
            arr.appendleft(arr.pop())
            answer += 1
    arr.popleft()

print(answer)

• index(x[, start[, stop]])
  • deque에 있는 x의 위치 반환

• popleft()
  • deque의 왼쪽에서 요소를 제거하고 반환

 

 

 

개선할 점

deque의 회전을 while문으로 구현했으나, 이를 deque 객체가 지원하는 rotate 메서드로 대체가능하다. 

• rotate(n=1)
  • deque를 n단계 오른쪽으로 회전. n이 음수이면 왼쪽으로 회전

from collections import deque

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

answer = 0
arr = deque(range(1, n + 1))

for pick in pick_list:
    idx = arr.index(pick)
    if idx <= (len(arr) // 2):
        arr.rotate(-idx)
        answer += idx
    else:
        arr.rotate(len(arr) - idx)
        answer += len(arr) - idx
    arr.popleft()

print(answer)

 

실행 시간도 개선할 수 있었다~