백준 / 1021번 / 회전하는 큐 / python 파이썬

 

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

 

 

덱 자료구조를 활용해 구현하면 쉽게 풀 수 있는 문제이다.  큐는 선입선출 방식이지만 덱은 양방향으로 삽입과 삭제 ( popleft, appendleft )가 가능하며,   시간 복잡도가 O(1)이다. 

 

코드

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
num = list(map(int, input().split()))
q = deque(_ for _ in range(1, N + 1))

count = 0
for i in num:
    while True:
        if q[0] == i:
            q.popleft()
            break
        else:
            if q.index(i) < len(q) / 2:
                while q[0] != i:
                    q.append(q.popleft())
                    count += 1
            else:
                while q[0] != i:
                    q.appendleft(q.pop())
                    count += 1
print(count)