BOJ 1021번: 회전하는 큐

www.acmicpc.net/problem/1021

1021번: 회전하는 큐

아이디어: #덱

뽑고자 하는 원소가 맨 첫번째 원소가 될때까지 왼쪽이나, 오른쪽으로 이동시키는 최소 횟수를 구하면 된다.

근데 그 최소횟수는 어떻게 구하지? 덱에서의 해당 원소의 위치를 알아야 할 것 같은데.. -> index(x)

index(x)<=len(덱)//2 -> popleft() 반대면 pop() 을 한다.

이 값이 뽑고자 하는 원소와 일치하지 않으면 각각 반대편에 다시 추가하고, ans+=1한다.

같은 경우 popleft()때는 그냥 break 하면 되지만, pop()의 경우에는 ans+=1을 하고 break 해야 한다.

 

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

d = deque()
for i in range(1, n+1):
    d.append(i)
ans = 0

for i in arr:
    if (d.index(i)<=len(d)//2):
        while (True):
            temp = d.popleft()
            if (temp==i):
                break
            else:
                d.append(temp)
                ans+=1
    else:
        while(True):
            temp = d.pop()
            if (temp==i):
                ans+=1 #pop()을 한 경우에 카운트를 한 번 더 해야한다.
                break
            else:
                d.appendleft(temp)
                ans+=1
print(ans)