[백준 1021] 회전하는 큐

1021번: 회전하는 큐

알고리즘 : 덱

난이도 : 실버Ⅲ

 

1. 문제요약

• N개의 원소를 갖는 양방향 순환 큐에서 입력으로 주어진 위치의 M개의 원소를 순서대로 뽑아내려 하는 상황이다.
• 다만 뽑을 수 있는 원소는 첫번째 원소뿐이어서 뽑으려는 원소를 첫번째 위치로 옮겨줘야 하는데, 이때 1) 큐 원소전체를 오른쪽으로 한칸 옮기거나 또는 2) 왼쪽으로 한칸 옮기는 연산이 가능하다. 이때 최소연산수를 구해야 한다.
• 시간제한은 2초이고 N은 50보다 작거나 같은 자연수이고 M은 N보다 작거나 같은 자연수 이다. N,M의 크기가 작으므로 연산마다 새로운 덱을 생성해도 무방해 보인다.

2. 구현과정

• N,M을 input으로 받고, 1부터 N까지로 이루어진 덱을 생성한다. 그냥 리스트로 구현해도 무방할 것이다.
• 뽑으려는 원소의 위치도 list(map(int,input().split()))을 통해 wanted 리스트로 저장해 준다.
• wanted 리스트를 순회하면서 idx를 추출하고, 현재 덱에서의 idx 위치를 now에 저장한다.
• 현재 덱에서 now를 기준으로 left, right로 분할한다. right에는 now를 포함하지 않도록 한다.
• 이제 answer에 왼쪽과 오른쪽중 어느방향으로 연산할지 정해야 하는데, left의 길이와 right의 길이+1중에서 더 작은쪽을 answer에 더해준다. right는 now를 포함하지 않으므로 +1을 한 것이다.
• 덱을 새로운 덱인 right + left로 업데이트 한다.

3. 파이썬 코드

N, M = map(int, input().split())
deq = [i for i in range(1, N + 1)]
wanted = list(map(int, input().split()))
answer = 0
for idx in wanted:
    now = deq.index(idx)
    left, right = deq[:now], deq[now + 1:]
    answer += min(len(left), len(right) + 1)
    deq = right + left
print(answer)