[ BAEKJOON ] No. 1021 회전하는큐

문제 )

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

1021번: 회전하는 큐

 

[ 풀이 ]

 

문제 이해를 하는 것이 제일 우선!

문제 이해를 위해 Algorithm의 Flow를 작성해보았다.

예제 2번에 대한 flow이다

 

뽑아내려는 원소의 위치가 queue의 중간위치보다 
✔  왼쪽에 위치하면 왼쪽으로 원소들을 이동시키는것이 더 편리할 것이고 → Leftmove Function
✔  오른쪽에 위치한다면 오른쪽으로 원소들을 이동시키는 것이 더 편리할 것이다.→ Rightmove Fuction

 

< 전체적인 Algorithm의 흐름>

✔  뽑아내려는 원소의 위치가 들어있는 list → arr
✔  1부터 N까지의 값이 들어있는 회전큐 list → queue
✔  count =0

1. arr 원소들에 하나씩 접근한다 →  i
         1-1)
         if arr의 원소가 queue의 중간보다 앞에 위치하는 경우,
                      Ⅰ. 우리가 찾는 원소(i) 가 나올때까지 Leftmove 해주기
                      Ⅱ.  count 증가 
         else arr의 원소가 queue의 중간보다 뒤에 위치하는 경우,
                      Ⅰ. 우리가 찾는 원소(i) 가 나올때까지 Rightmove 해주기
                      Ⅱ.  count 증가 
   
         1-2)
         queue의 제일 앞 원소를 없애준다 (popleft 해주기)
         [ queue의 제일 앞 원소 = 우리가 찾는 값 (i) 이므로 ]

 

 

- python code

from collections import deque

# 전체적인 Algorithm의 흐름나타내는 Function
def First(N,arr):
    count=0
    queue=deque([i for i in range(1,N+1)]) 
    for i in arr:
        if queue.index(i)<=(len(queue)//2): #arr의 원소가 queue의 중간보다 앞에 위치
            while queue[0]!=i:
                Leftmove(queue) #i가 나올때까지 Leftmove
                count+=1        
        else: # arr의 원소가 queue의 중간보다 뒤에 위치
            while queue[0]!=i:
                Rightmove(queue) #i가 나올때까지 Rightmove
                count+=1       
        queue.popleft()  #queue의 제일 앞 원소 pop
    return count


def Leftmove(arr):
    mid=arr.popleft()
    arr.append(mid)

def Rightmove(arr):
    mid=arr.pop()
    arr.appendleft(mid)


N,M=map(int, input().split())
p=list(map(int,input().split()))
print(First(N,p))