[BOJ] 1021번: 회전하는 큐

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

 

 

문제

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

 

풀이

문제 이름은 '큐'이지만, 사실 덱을 활용하는 문제이다. 3번 연산에서 pop, appendleft가 사용되기 때문이다.

처음에 문제를 제대로 이해하지 못했는데, 1부터 N까지의 수가 있는 덱에서 2, 3번 연산을 활용하여 두번째 줄에 입력된 순서로 뽑아내라는 것이다. 이때 2, 3번의 연산 횟수를 출력하면 된다.

 

from collections import deque

N, M = map(int, input().split())
target = deque(map(int, input().split()))
Deq = deque(i for i in range(1, N + 1))
cnt = 0

while target:
    if target[0] == Deq[0]:
        Deq.popleft()
        target.popleft()
    else:
        if Deq.index(target[0]) <= len(Deq) // 2:
            Deq.append(Deq.popleft())
        else:
            Deq.appendleft(Deq.pop())
        cnt += 1
print(cnt)

1. 덱을 활용하기 위해 import

2. N, M, target을 입력받음

3. N개의 원소를 포함하는 덱 생성

4. 연산횟수인 cnt를 0으로 초기화

5. target이 존재하면 반복문 실행

6. 만약 target과 Deq의 가장 왼쪽 수가 동일하면 뽑아냄.

7. 동일하지 않다면, 뽑아야하는 수가 왼쪽입구와 가까운지, 오른쪽입구와 가까운지 확인 후 입구쪽으로 옮김 -> cnt 증가

8. cnt 출력