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

1021번: 회전하는 큐

문제

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

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

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

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

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

 

과정

1. 큐의 크기 n과 뽑고싶은 원소의 개수 m을 입력받는다.
2. 주어진 3개의 연산을 활용하여 n개의 원소중 입력된 m개의 원소를 삭제하는 최소 연산 횟수를 구하는 문제이다.
       1) 첫 번째 원소 삭제
       2) 첫 번째 원소를 맨 끝으로 이동
       3) 마지막 원소를 맨 앞으로 이동
3. 이때 연산 횟수에는 두 번째, 세 번째 연산을 할때만 포함된다.
4. 입력받은 길이를 이용해 deque을 만들어준다
5. 가장 앞에 값을 확인 후 원하는 원소와 값이 다르면 맨뒤로 보내고 움직인 횟수를 늘려준다. (2번 연산)
6. 3번 연산은 2번 연산과 정반대의 연산이기 때문에 전체 길이에서 2번 연산을 빼준 값이 된다.
7. 반복 후 가장 작은 값을 정답에 넣어서 출력한다.

 

예제 입력

10 3
1 2 3

예제 출력

0

 

풀이

from collections import deque

n, m = map(int, input().split())
orders = list(map(int, input().split()))
deck = deque(range(1, n + 1))
ans = 0
for order in orders:
    moved_right = 0
    while deck[0] != order:
        deck.append(deck.popleft())
        moved_right += 1
    deck.popleft()
    moved_left = n - moved_right
    ans += min(moved_left, moved_right)
    n -= 1
print(ans)

 

한 줄씩 해석해보기

n, m = map(int, input().split())

• 길이와 뽑아 내려하는 수의 개수를 입력받는다

orders = list(map(int, input().split()))

• 뽑아내려고 하는 수를 입력받은 후 리스트에 저장한다.

deck = deque(range(1, n + 1))
ans = 0

• 입력받은 길이를 이용해 덱을 만들어준다
• 정답을 입력받을 변수를 만들어준다

for order in orders:
    moved_right = 0

• 리스트에 저장된 수들을 for문
• 2번연산을 이용해 이동할 횟수 변수를 만들어준다.

while deck[0] != order:
	deck.append(deck.popleft())
	moved_right += 1

• 지금 바라보는 원소가 첫번째 원소가 될때까지 맨앞에 숫자를 맨뒤로 이동시키고 움직인 횟수를 더해준다.

deck.popleft()

• 입력받은 값과 맨앞에 온 값이 같은 경우 제거해준다.

moved_left = n - moved_right
ans += min(moved_left, moved_right)
n -= 1

• 3번 연산은 2번 연산을 반대로 했을 경우와 같기 때문에 전체 길이에서 2번연산을 통해 움직인 횟수를 뺀 값을 저장해준다.
• 정답에 2번과 3번 연산 중 최소값을 넣는다.
• 수를 하나 제거했기 때문에 전체 길이에서 -1 해준다.

pring(ans)

• 모든 수를 찾을 때까지 반복 후 정답을 출력한다.