[백준] 1021번 (python 파이썬)

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

 

ex)

10 3

2 9 5

 

2

queue = 1 2 3 4 5 6 7 8 9 10

왼쪽으로 회전 1번

queue = 2 3 4 5 6 7 8 9 10 1

pop

 

9

queue = 3 4 5 6 7 8 9 10 1

오른쪽으로 회전 3번

queue = 9 10 1 3 4 5 6 7 8

pop

 

5

queue = 10 1 3 4 5 6 7 8

오른쪽으로 회전 4번

queue = 5 6 7 8 10 1 3 4

pop

 

총 횟수 8번

 

핵심은 오른쪽으로 회전할지 왼쪽으로 회전할지 정하는 것이다.

타겟에 대해 index를 계산하여 판단한다.

 

from collections import deque
import sys

input = sys.stdin.readline
n, m = map(int, input().split())
targets = list(map(int, input().split()))
temp = list()
for i in range(1, n+1):
    temp.append(i)
queue = deque(temp)

def moveLeft(queue : deque):
    queue.append(queue.popleft())
    return queue

def moveRight(queue : deque):
    queue.appendleft(queue.pop())
    return queue

count = 0

for i in range(m):
    target = targets[i]
    left_move_count = queue.index(target)
    right_move_count = len(queue) - queue.index(target)
    while target != queue[0]:
        if left_move_count >= right_move_count:
            for _ in range(right_move_count):
                queue = moveRight(queue)
                count += 1
        else:
            for _ in range(left_move_count):
                queue = moveLeft(queue)
                count += 1
    queue.popleft()

print(count)