[백준] 1021 파이썬(python) : 회전하는 큐

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

1021번: 회전하는 큐

 

 

입력값 n을 받으면 1~n까지 있는 리스트에서 입력받은 숫자들 빼주는데 왼쪽에서만 뺄 수 있고(1번 연산) 왼쪽으로 넘기거나(3번 연산) 오른쪽으로 넘기면서(2번 연산) 2, 3번 연산의 횟수를 세어주어야 한다.

 

즉 n = 10이면 1, 2, 3, 4, 5, 6, 7, 8, 9, 10이 있는 리스트에서 입력 받은 2 9 5를 빼주기 위해 몇번은 2, 3번 연산을 해주어야 하느냐이다.

 

2를 빼주기 위해선 오른쪽으로 넘기는 연산을 한번 하고 (2번 연산) 2, 3, 4, 5, 6, 7, 8, 9, 10, 1 이 상태에서 가장 왼쪽의 원소를 빼주는 1번 연산 수행 3, 4, 5, 6, 7, 8, 9, 10, 1이 된다. 이후에 반복해서 9와 5를 빼주는 과정에서 2, 3번 연산의 횟수를 세어주면 된다.

 

from collections import deque
n, m = map(int, input().split())
number = list(map(int, input().split()))
data = deque(list(range(1, n+1))) #1
cnt = 0
for num in number:
    while True:
        if data[0] == num:
            data.popleft() #2
            break
        else:
            if len(data)//2 >= data.index(num): #3
                data.rotate(-1)
                cnt += 1
            else: #4
                data.rotate(1) 
                cnt += 1
print(cnt)

 

#1 : 값을 빼줄 리스트 생성

#2 : 1번 연산

#3 : 2번 연산

#4 : 3번 연산

 

deque의 rotate함수를 사용하는 방법을 소개하는 글을 링크 걸어놓겠다.

https://hgk5722.tistory.com/182

[Python] deque를 사용한 1차원 리스트 회전하기