백준 - 1021번(덱)

파이썬의 deque 기능은 원형 큐와 비슷한 모습을 구현할 수 있다.

양쪽에서 값을 넣는 것이 가능하기 때문이다.

 

1 2 3 4 5 6 7 8 9

 

list.appendleft(list.pop()) 을 사용하면 시계 방향(내림차순)

list.append(list.leftpop()) 을 사용하면 반시계 방향으로 탐색이 된다.(오름차순)

 

이번 문제의 핵심아이디어는 시계방향과 반시계 방향 중에 어디로 탐색하는 것인지 더 효율적인가에 대한 기준이 필요한 문제였다.

index 기능이 시간복잡도에서 손해일 거라 생각해서 고려하지 않았지만 이게 정답이었다.

 

찾고자 하는 값의 index값이 전체 배열의 길이의 절반보다 작으면 반시계(오름차순)으로 찾는 게 효율적이고

index 값이 배열 길이 절반보다 크면 시계(내림차순)로 찾는 게 효율적이다.

 

import sys
from collections import deque

n,m = sys.stdin.readline().split()
ans = []
ans.append(sys.stdin.readline().split())
arr = deque()

for i in range(1,int(n)+1):
    arr.append(i)

cnt = 0


for i in ans[0]:
    if arr.index(int(i)) <= len(arr)/2: #순서대로
        while 1:
            if arr[0] == int(i):
                arr.popleft()
                tmp = i
                break
            arr.append(arr.popleft())
            cnt = cnt+1

    elif arr.index(int(i)) >= len(arr)/2: #역순
         while 1:
            if arr[0] == int(i):
                arr.popleft()
                tmp = i
                break
            arr.appendleft(arr.pop())
            cnt = cnt+1

print(cnt)