boj_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번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입력

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

출력

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

 

 

문제풀이

문제에서 주어진 것처럼, 3가지 연산을 수행할 수 있다. 첫 번째는 가장 첫 번째 원소를 뽑는 것이고, 두 번째는 쉽게 말해 첫 번째 원소를 맨 뒤로 보내는 것이다. 마지막으로 두 번째는 마지막 원소를 첫 번째 원소의 자리로 옮기는 것이다. 우리가 구해야 하는 것은 2, 3번째 연산을 최소로 사용해서 원하는 숫자를 뽑는 것이다. 

 

먼저 주어진 N을 통해 큐의 크기에 맞는 deque를 만들어 준다.

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
deq = deque(range(1, N+1))
print(deq)


>> deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

 이렇게 deque를 만들면 뽑으려고 하는 원소 그대로를 선정해 뽑을 수 있다. 인덱스로 접근하기도 편리하다.

 

그 다음 두 번째 줄의 주어진 숫자 또한 deque로 만든다.

p = deque(map(int,input().split())
print(p)

>> deque([1, 2, 3])

 

이제 처음만들어 놓은 deq리스트와 우리가 뽑아야할 p 리스트를 적절히 사용하여 최소의 연산을 실행하는 경우를 구해주면 된다.

# 먼저 뽑아야할 원소를 선정한다

# 연산 카운트
ans = 0

# p = deque([1, 2, 3])
for i in p:
	#원하는 원소가 뽑힐 때 까지,
    while True:
    	if deq[0] == i:      # deq의 첫 번째 원소가 뽑아야할 원소와 같다면
        	deq.popleft()    # 원소 추출
            break            # while문 종료
        else:
        	# 우리가 뽑아야할 원소의 위치가, deq 리스트의 중간 지점에서 보다 왼쪽에 있다면
            # 왼쪽으로 옮기는 것(2번째 연산)이 최소이므로, 2번째 연산을 실행한다
        	if deq.index(i) < len(deq) / 2:
            	while deq[0] != i:
                	deq.append(deq.popleft())  # 2번째 연산
                    # 연산 카운트
                    ans += 1
            else:
            	# 그 반대일 경우
                while deq[0] != i:
                	deq.appendleft(deq.pop())   # 3번째 연산
                    ans += 1

print(ans)

 

처음에 이것저것 삽질을 해보다가 deq리스트의 길이와 뽑아야할 원소의 인덱스 위치로 판별하는 아이디어는 전혀 생각하기 못했다.. 결국 구글링을 통해 다른 분들이 풀이하는 것을 보고 이해할 수 있었다.

 

코드를 작성하다보면 매번 삽질을 하고, 코드가 스파게티가 되어버리고 산으로 가는 경우가 있는데 요즘 들어 코드 작성전 구상하는것이 얼마나 중요한지 느끼고 있다.