백준 1021 python

문제 링크

Queue 하나를 주고, 3가지 연산들을 준다.

1. 맨 앞의 단어를 빼기.
2. 맨 앞의 단어를 빼서 뒤로 붙이기.
3. 맨 뒤의 단어를 빼서 앞으로 붙이기.

초기 Q 안에는 숫자 1부터 N까지 들어가있고, M개의 숫자를 차례대로 빼려고 한다. 이 때 2번과 3번 연산이 일어나는 최소값을 구하는 문제.

input : 
N M
(N 이하의 구별되는 M개의 숫자들)

output : 
(최소 작동횟수)

deque를 이용해서 간단히 구해봤다.
첫 번째 연산이야 그냥 Q.popleft()를 사용하기 때문에 따로 함수를 만들지 않았고, 2,3번 연산에 대한 함수를 구현했다.
(feat. micro service의 중요성을 되새김질하며..)

그 후 input을 받는 코드를 짜고, 어떻게 구현하면 좋을지 정말 약간 고민해봤다. 어차피 다음 뺄 숫자가 정해지면 2번 연산을 하던지 3번 연산을 하던지 하나만 할꺼이니 index를 통해 좌우 길이를 생각해주고 로직을 만들었다.

결과코드

from sys import stdin
from collections import deque

def sec_proc(Q,n):
    for _ in range(n):
        Q.append(Q.popleft())
    
def thr_proc(Q,n):
    for _ in range(n):
        Q.appendleft(Q.pop())

N,M = map(int,stdin.readline().strip().split())
cnt = 0
nums = tuple(map(int,stdin.readline().strip().split()))
idx = 0

Q = deque()
for i in range(1,N+1):
    Q.append(i)

for _ in range(M):
    left = Q.index(nums[idx])
    right = len(Q)-left
    if right>=left:
        cnt += left
        sec_proc(Q,left)
    else:
        cnt += right
        thr_proc(Q,right)
    Q.popleft()
    
    idx += 1

print(cnt)