[백준/파이썬] 1021번

📍백준 1021번 문제

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

코드

from collections import deque
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
tem = list(map(int, input().split()))
li = deque([])
cnt = 0
for i in range(n):
    li.append(i+1)
for i in tem:
    temp = li.index(i)
    if temp <= len(li)/2:
        while True:
            if i == li[0]:
                li.popleft()
                break
            else:
                li.append(li.popleft())
                cnt += 1
    else:
        while True:
            if i == li[0]:
                li.popleft()
                break
            else:
                li.appendleft(li.pop())
                cnt += 1

print(cnt)

풀이

deque를 이용해서 풀면 된다.
최소한으로 큐를 움직여야 하므로 원하는 값의 위치에 따라 오른쪽으로 움직일지 왼쪽으로 움직일지 결정하면 된다.
간단하게 값이 큐의 중간위치(길이의 절반)보다 오른쪽에 있으면 값의 위치가 li[0]에 있을때까지 오른쪽으로 이동 (pop후 appendleft), 왼쪽에 있으면 값의 위치가 li[0]에 있을때까지 왼쪽으로 이동한다(popleft후 append).