[백준] 1021번 회전하는 큐 (Python 파이썬)

문제 설명

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

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

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

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

---

풀이 과정

처음 문제를 보고 잘못 이해했던 점이, 자신이 뽑으려는 수가 아니더라도 1번을 이용해 큐를 줄여갈 수 있는 줄 알았다. 하지만 자신이 뽑으려는 수가 첫 번째 원소일 때만 1번을 사용하여 원소를 뽑아낼 수 있다.

 

pick 리스트에는 자신이 뽑고자 하는 원소들의 최초 위치가 들어있다.

큐에는 1부터 N까지의 원소들이 들어있다.

 

입력한 순서대로 원소를 뽑아내야 하므로 pick[0]이 현재 뽑아내야 할 원소의 최초 위치이다.

그래서 큐의 첫 번째 원소와 pick의 첫 번째 원소가 일치하면 1번 과정을 통해 원소를 뽑아내게 되는 것이다.

 

그 외의 경우에는 2, 3번의 연산을 반복해야 하는데, 최소한의 연산을 해야하므로

현재 뽑고자 하는 원소가 왼쪽에 더 가까운지 오른쪽에 더 가까운지를 파악하여

2, 3 과정을 선택하여 수행하면 된다. 과정 수행 후에는 횟수를 하나씩 늘려간다.

 

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
pick = list(map(int, sys.stdin.readline().split()))

queue = deque([i for i in range(1, n+1)])
cnt = 0


while pick:
    if queue[0] == pick[0]:
        queue.popleft()
        del pick[0]
    else:
        if queue.index(pick[0]) > len(queue) / 2:
            while queue[0] != pick[0]:
                queue.appendleft(queue.pop())
                cnt += 1
        else:
            while queue[0] != pick[0]:
                queue.append(queue.popleft())
                cnt += 1

print(cnt)

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !