[백준_python] 회전하는 큐 || 1021(global, deque.rotate())

www.acmicpc.net/problem/1021

1021번: 회전하는 큐

2번 연산은 1 2 3 -> 2 3 1
3번 연산은 1 2 3 -> 3 1 2
뽑으려는 값이 큐의 첫 번째 요소가 될 때까지 둘 연산을 각각 반복하고 그 중에 최소값을 선택하여 합하면서
총 연산의 최소 횟수를 구해준다.

# 회전하는 큐

n, m = map(int, input().split(' '))  # n : 큐의 크기, m : 몇 번 뽑아낼 건지
arr = list(map(int, input().split(' ')))  # m번동안 어느 위치를 뽑아낼 건지

num2 = [i+1 for i in range(n)]  #두 번째 연산을 할 큐
num3 = [i+1 for i in range(n)]  #세 번째 연산을 할 큐
result = 0  # 연산의 최솟값(결과)

for i in arr:
    cnt2 = cnt3 = 0
    while True:  #두 번째 연산
        if num2[0] == i:
            num2.pop(0)
            break
        num2.append(num2.pop(0))
        cnt2 += 1
    while True:  #세 번째 연산
        if num3[0] == i:
            num3.pop(0)
            break
        num3.insert(0, num3.pop())
        cnt3 += 1
    result += min(cnt2, cnt3) # 두 방법 중 작은 값 선택

print(result)

---

다른 분의 코드를 보다가, global이라는 변수를 이용해 주는 것을 보게 되어서 추가..!
global은 전역 변수이다. 
보통 함수 안에 선언된 변수는 함수 밖에서 사용되지 못하는데, global로 전역변수를 선언해주면,
함수 밖에서도 사용이 가능하다.
이를 이용해, 2번째와 3번째 연산을 함수로 표현해주었다.
위 코드에서는 둘 연산을 다 해주고 난 후 그 중에 최소값을 합하는 식이였지만,
아래에서의 코드는 어느 쪽이 더 최소인지 판단하고 계산을 해주게 된다.

# 회전하는 큐_2

def cnt2(que):  # 123 -> 231
    global cnt
    que.append(que.pop(0))
    cnt += 1


def cnt3(que):  # 123 -> 312
    global cnt
    que.insert(0, que.pop())
    cnt += 1


n, m = map(int, input().split(' '))  # n : 큐의 크기, m : 몇 번 뽑아낼 건지
arr = list(map(int, input().split(' ')))

num = [i for i in range(1, n+1)]  # 큐
cnt = 0

while arr:
    if num[0] == arr[0]:
        num.pop(0)
        arr.pop(0)
    else:
        if num.index(arr[0]) <= len(num)//2:  # 뽑아내려는 값의 위치가 큐의 반보다 작은 경우
            while num[0] != arr[0]:
                cnt2(num)
        else:
            while num[0] != arr[0]:
                cnt3(num)

print(cnt)

---

또한, 덱의 내장 함수 rotate( )에 대해서도 알게 되었다.
음수면 왼쪽, 양수면 오른쪽으로 값만큼 회전시켜준다.

# 회전하는 큐_3

from collections import deque

n, m = map(int, input().split(' '))  # n : 큐의 크기, m : 몇 번 뽑아낼 건지
arr = list(map(int, input().split(' ')))

que = deque(range(1, n+1))

cnt = 0

for i in arr:
    if i == que[0]:
        que.popleft()
        continue

    q_idx = que.index(i)

    if q_idx <= len(que)//2:
        que.rotate(-q_idx)
        cnt += q_idx

    else:
        que.rotate(len(que)-q_idx)
        cnt += len(que)-q_idx
        
    que.popleft()
print(cnt)

 
 
 
 
참고한 사이트)
roseline124.github.io/algorithm/2019/04/06/Altorithm-baekjoon-1021.html

유혹하는 개발하기

inspirit941.tistory.com/176

[Python] 백준 1021. 회전하는 큐