백준1021 - 회전하는 큐 (덱) python

https://www.acmicpc.net/problem/1021

문제를 읽자마자, 자료구조 덱을 활용한 문제라는 것을 파악했고, 내게 떠오른 언어는 다양한 자료 구조를 모듈로 불러와 사용할 수 있는 파이썬이었다. 근래의 포스팅 대부분이 자바스크립트로 작성된 포스팅이라는 것을 핑계로 이번 포스팅은 파이썬으로 작성한다.

 

문제 풀이 방식

앞서 얘기한 바와 같이 해당 문제는 자료구조 덱으로 구현이 가능하다.

여기서 중요한 점은 연산의 최소횟수를 구해야 한다는 점인데, 이는 해당 덱에서 가지고 있는 원소의 양의 중앙값, 구하고자 하는 원소의 인덱스값을 비교하여 2번 연산을 할 것인지 3번 연산을 할 것인지 결정할 수 있도록 했다.

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

from collections import deque

def solution (data) :
  [[N,M], arr] = list(map(lambda x : list(map(int, x.split())), data))
  queue = deque([v for v in range(1, N+1)])
  
  result = 0
  
  for i in range(M) :
    target = queue.index(arr[i])
    reduce = True if len(queue) // 2 >= target else False
    
    while queue[0] != arr[i] :
      if reduce : 
        item = queue.popleft()
        queue.append(item)
      else :
        item = queue.pop()
        queue.appendleft(item)
        
      result += 1

    queue.popleft()
        
  print(result)
  
solution(input_data)