1021번 - 회전하는 큐

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

1021번: 회전하는 큐

요즘 자료구조 문제를 많이 푸는 것 같다. 이 문제는 회전하는 큐를 덱으로 구현하는 문제이다.

idx라는 변수를 두어 answer에 넣어야 하는 수가 무엇인지 검사하였다. (입력의 num 배열로)

만약 아니라면, 1번 연산을 다시 되돌리고 찾고자 하는 수의 위치를 찾는다.

인덱스가 앞쪽이면 2번 연산을, 뒤쪽이면 3번 연산을 수행한다.

이때 인덱스 비교를 할 때 // 대신 / 를 써야 한다.

Q의 길이가 홀수일 때 앞쪽에 두는 게 더 빠르기 때문이다.

예를 들어, [1, 2, 3, 4, 5] 가 있고 3을 찾고자 하면 앞쪽은 [1, 2, 3]이고 뒤쪽은 [4, 5]이다.

그러고 3번을 앞으로 뽑으면 2번의 연산을 하면 되지만 / 뒤로 뽑으면 3번의 연산을 해야 한다.

따라서 Q의 길이가 홀수일 때 실수형으로 나오게 하면, 중간값이 앞쪽에 속하게 된다.

# 회전하는 큐
import sys
input = sys.stdin.readline
from collections import deque

N, M = map(int, input().split())
num = list(map(int, input().split()))
answer = []
cnt = 0
Q = deque([i for i in range(1, N+1)])

while True:
    if answer == num:
        print(cnt)
        break
    idx = len(answer)
    while True:
        q = Q.popleft() # 1
        if q == num[idx]:
            answer.append(q)
            break
        else:
            Q.appendleft(q) # 원래대로
            if Q.index(num[idx]) < len(Q) / 2:
                Q.append(Q.popleft()) # 2
                cnt += 1
            else:
                Q.appendleft(Q.pop()) # 3
                cnt += 1