백준 1021 회전하는 큐 파이썬

문제

1021번: 회전하는 큐

덱을 활용해서 푸는 문제이다.

 

 

문제 요약 

3가지 연산

(1) 첫번째 원소 추출

     a1 a2 .. ak → a2 .. ak

(2) 왼쪽 한 칸 이동

      a1 a2 .. ak → a2 .. ak a1

(3) 오른쪽 한 칸 이동

      a1 a2 .. ak → ak a1 .. ak-1

 

입력

큐의 크기 n, 뽑아내려는 수 개수 m

뽑아내려는 수의 위치

 

출력

원소를 주어진 순서로 뽑는데 드는 2,3번 연산 최소값

 

 

예제

10 3

2 9 5

 

1 2 3 4 5 6 7 8 9 10

(2) 2 3 4 5 6 7 8 9 10 1

(1) 3 4 5 6 7 8 9 10 1

(3)

(3) 10 1 3 4 5 6 7 8 9

(3) 9 10 1 3 4 5 6 7 8

(1) 10 1 3 4 5 6 7 8

(3)

(3)

(3)

(3) 5 6 7 8 10 1 3 4

(1)

 

왼쪽, 오른쪽 이동이 8번 필요하다. (2)+(3)=8

 

 

슈도 코드

찾는 수를 첫 번째 인덱스로 위치 시켜야 한다.

 

중앙을 기준으로 왼쪽에 있으면 왼쪽으로 이동하는게 최적의 해이다.

반대로 중앙을 기준으로 오른쪽에 있으면 오른쪽으로 이동시켜야 한다.

 

1 2 3 4 5 6 7 8 9 

5를 1로 위치시킨다고 가정해보자.

왼쪽으로는 4번, 오른쪽으로는 5번 이동해야 한다. 따라서 왼쪽 이동이 바람직하다.

 

이처럼 큐의 크기가 홀수 일 때를 고려해,  찾는 수 인덱스에 1을 더하였다.

 

2,3 번 연산의 총 횟수를 구해야 하므로 해당 연산마다 cnt를 더해준다.

찾는 수 인덱스 + 1 <= 덱의 수 / 2
	수가 첫번째 놓일 때까지 2번 연산 (왼쪽 이동)
	cnt++
찾는 수 인덱스 > 덱의 수 / 2
	수가 첫번째 놓일 때까지 3번 연산 (오른쪽 이동)
	cnt++
첫번째 자리에 놓이면 1번 연산

 

 

제출코드

import sys
from collections import deque

deq = deque()
n, m = map(int, sys.stdin.readline().split())
for i in range(n):
    deq.append(i + 1)

key = sys.stdin.readline().split()
cnt = 0

for i in range(m):
    k = int(key[i])
    if deq.index(k)<= len(deq) // 2:
        while deq.index(k) != 0:
            deq.append(deq.popleft())  # 왼쪽 이동
            cnt += 1
        deq.popleft() # 2번연산
    else:
        while deq.index(k) != 0:
            deq.appendleft(deq.pop()) # 오른쪽 이동
            cnt += 1
        deq.popleft() # 3번 연산

print(cnt)