[백준알고리즘] 1021번: 회전하는 큐 -Python

[백준알고리즘] 1021번: 회전하는 큐 -Python

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

1021번: 회전하는 큐

저번에는 덱을 c언어로 직접 구현해봤기 때문에 이번에는 그냥 Python으로 풀어봤다.

 

Python에서 제공하는  collections 모듈의 deque을 이용하면 2, 3번 기능인 rotate기능까지 제공하기 때문에 쉽게 문제를 풀 수 있다.

 

 

왼쪽 값을 오른쪽으로 붙이는 rotate 할지 오른쪽 값을 왼쪽으로 붙이는 rotate 할지는 아이디어가 필요하다.

 

여기서 왼쪽의 값들을 오른쪽으로 rotate하는 것은 rotate() 안에 -로 개수가 들어가야 하며 오른쪽 값들을 왼쪽으로 rotate 시킬 때에는 +값으로 개수를 나타내면 된다.

따라서 왼쪽에서부터 pop시킬 값을 찾은 인덱스가 i일 때 rotate 시키는 방법은 i만큼 앞에서부터 뒤로 rotate 시키거나 len(deque)-i만큼 뒤에서 앞으로 rotate 시키는 것이다. 그래서 두 개의 값 -i와 len(deque)-i 중 작은 값을 i로 하고 rotate(i)를 하면 된다.

 

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
Q = deque()
for i in range(N):
    Q.append(i+1)
want = map(int, sys.stdin.readline().split())

total = 0
for w in want:
    i = 0
    while w != Q[i]:
        i += 1
    i = len(Q) - i if len(Q) - i < i else -i
    Q.rotate(i)
    total += abs(i)
    Q.popleft()

print(total)

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다