[백준] 1021번 : 회전하는 큐

1021번: 회전하는 큐 (acmicpc.net)

1021번: 회전하는 큐

 

 

문제를 간단히 설명하자면 양쪽으로 stack 과 pop이 가능한 양방향 순환 큐가 있다.

이때 입력 받는 값이 큐의 크기 N, 뽑아내려고 하는 수의 개수 M, 뽑아내려는 하는 수의 위치 , 즉 뽑아내려는 수의 index 가 있다.

 

큐는 보통 리스트를 사용하는데 양방향에서 수를 넣고 빼야 하기 때문에 그것이 가능한 deque 를 사용한다. 

큐의 크기 N 이 주어지면 deque의 크기를 설정하고 범위를 N만큼 순차적으로 정수를 저장한다.

그리고 M을 통해 몇개의 숫자를 뽑을 것인지 알 수 있으며 index에서 지정된 수를 뽑되,

pop을 할 수 있는 위치는 쳣번째 원소 위치이다.

그래서 index 위치가 첫번째 윈소에 가까워 지도록 움직여 줘야한다.

위치에 따라 오른쪽으로 이동하거나 왼쪽으로 이동시켜 첫번째 원소가 되게 끔 만들어 준다.

 

stack 문제가 나오면 거의 다 list를 사용했었는데

deque 라는 라이브러리를 사용한다면 간단하게 풀 수 있는 문제인 것 같다.

근데 이 개념을 모르고 봐서 그런지 문제가 어렵게 느껴졌다.

 

이번 문제에서 알고 넘어 가야할 것은 deque라이브러리의 사용이다.

from collections import deque
 
n, m = map(int, input().split())
target_indexes = list(map(int, input().split()))
cnt = 0
arr = deque([i for i in range(1, n+1)])
 
for target in target_indexes:
    while True:
        if arr[0] == target:
            arr.popleft()
            break
        else:
            if arr.index(target) <= len(arr) // 2:
                arr.rotate(-1)
            else:
                arr.rotate(1)
            cnt += 1
print(cnt)