(Python) - BOJ(1021번) : 회전하는 큐

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

1021번: 회전하는 큐

 

• 해설 :

크기가 N인 큐에서 M개의 수를 뽑아내려고 한다. 뽑아내는 연산은 0번째 원소만 가능할 때, 큐를 왼쪽, 또는 오른쪽으로 한 칸씩 회전시키는 연산을 최소 몇 번 하여 뽑아내려는 값을 전부 뽑아낼 수 있는지 찾는 문제이다.

 

 

 

 

• 풀이 :

자료구조중 덱을 사용하여 구현하면 효율적으로 구현이 가능하다.

스택, 큐, 덱의 차이점은 아래 링크에 정리해 두었다.

 

(스택, 큐, 덱이란? : https://recordofwonseok.tistory.com/81?category=1002112)

 

 

왼쪽으로 회전시킬지 오른쪽으로 회전시킬지에 대한 판단은 중앙을 기준으로 왼쪽에 찾으려는 요소가 있는지 오른쪽에 있는지를 판단하여 결정해주었다.

 

 

 

 

n, m = map(int, input().split())
s = list(map(int ,input().split()))
q = [i for i in range(1, n + 1)]
cnt = 0
for i in range(m):
    q_len = len(q)
    q_index = q.index(s[i])
    if q_index < q_len - q_index:
        while True:
            if q[0] == s[i]:
                del q[0]
                break
            else:
                q.append(q[0])
                del q[0]
                cnt += 1
    else:
        while True:
            if q[0] == s[i]:
                del q[0]
                break
            else:
                q.insert(0, q[-1])
                del q[-1]
                cnt += 1
print(cnt)