[백준][1021] 회전하는 큐

• Problem Link : https://www.acmicpc.net/problem/1021

문제

• 양방향 순환 큐를 가지고 있다고 할 때 특정 위치에 있는 원소를 뽑아내려고 한다.
• 첫 번째 원소만을 뽑아낼 수 있다.
• 첫 번째 원소가 원하는 원소가 아니면 원소를 양방향으로 회전 시킬 수 있다.

입력

• 첫째 줄, 큐의 크기 N, 뽑아내려고 하는 수의 개수 M이 주어진다.
• 둘째 줄, 뽑아내려고 하는 수의 위치가 순서대로 주어진다.

출력

• 큐를 회전시킨 횟수를 출력한다.

풀이

먼저 회전한다는 개념이 결국 왼쪽으로 원소를 뽑아 오른쪽에 삽입, 오른쪽의 원소를 뽑아 왼쪽에 삽입을 해야한다는 뜻이고 이는 양방향 큐인 데큐(deque)를 이용해서 쉽게 구현할 수가 있을 것이라고 생각했다. 따라서 다음과 같은 과정을 거쳐 회전을 시키고 첫 번째 원소를 뽑아내는 과정을 반복한다.

• 첫 번째 원소가 원하는 원소인지 확인하고 뽑을지 말지를 결정
• 원하는 원소가 없다면, 뽑고 싶은 원소의 위치를 확인한다.
• 뽑고자 하는 원소가 앞쪽에 더 가깝다면? 왼쪽으로 회전
  - 왼쪽 원소를 뽑아 오른쪽에 삽입시켜 회전
• 뽑고자 하는 원소가 뒤쪽에 더 가깝다면? 오른쪽으로 회전
  - 오른쪽 원소를 뽑아 왼쪽에 삽입시켜 회전
  

이 때 회전시킬 때마다 카운트 값을 증가시키면 된다.

코드

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
pos = list(map(int, input().split()))
dq = deque(range(1, n + 1))

cnt = 0
for i in pos:
    while True:
        # 맨앞에 원하는 위치의 수가 있으면 popleft
        if dq[0] == i:
            dq.popleft()
            break
        else:
            # 앞쪽에 더 가깝다면 2번 방법 사용
            if dq.index(i) < len(dq) / 2:
                while dq[0] != i:
                    # 첫번째 자리에 올 때까지 2번 방법 사용
                    dq.append(dq.popleft())
                    cnt += 1
            # 뒤쪽에 더 가깝다면 3번 방법 사용
            else:
                while dq[0] != i:
                    # 첫번째 자리에 올 때까지 3번 방법 사용
                    dq.appendleft(dq.pop())
                    cnt += 1
print(cnt)