1021번: 회전하는 큐
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가
www.acmicpc.net
아이디어: #덱
뽑고자 하는 원소가 맨 첫번째 원소가 될때까지 왼쪽이나, 오른쪽으로 이동시키는 최소 횟수를 구하면 된다.
근데 그 최소횟수는 어떻게 구하지? 덱에서의 해당 원소의 위치를 알아야 할 것 같은데.. -> index(x)
index(x)<=len(덱)//2 -> popleft() 반대면 pop() 을 한다.
이 값이 뽑고자 하는 원소와 일치하지 않으면 각각 반대편에 다시 추가하고, ans+=1한다.
같은 경우 popleft()때는 그냥 break 하면 되지만, pop()의 경우에는 ans+=1을 하고 break 해야 한다.
import sys
from collections import deque
n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
d = deque()
for i in range(1, n+1):
d.append(i)
ans = 0
for i in arr:
if (d.index(i)<=len(d)//2):
while (True):
temp = d.popleft()
if (temp==i):
break
else:
d.append(temp)
ans+=1
else:
while(True):
temp = d.pop()
if (temp==i):
ans+=1 #pop()을 한 경우에 카운트를 한 번 더 해야한다.
break
else:
d.appendleft(temp)
ans+=1
print(ans)
'알고리즘💻 > 스택&큐&덱' 카테고리의 다른 글
BOJ 17299번: 오등큰수 (0) | 2021.02.01 |
---|---|
BOJ 2504번: 괄호의 값 (0) | 2021.02.01 |
BOJ 1966번: 프린터 큐 (0) | 2021.01.31 |
BOJ 1158번: 요세푸스 문제 / 파이썬 Queue (0) | 2021.01.31 |
BOJ 4949번: 균형잡힌 세상 (0) | 2021.01.31 |