162. 1021(회전하는 큐) - 파이썬

from collections import deque
from operator import indexOf
import sys
input = sys.stdin.readline

N, M = map(int, input().split())

num = deque(i for i in range(1, N+1))
innum = deque(list(map(int, input().split())))
cnt = 0

while True:
    if num[0] == innum[0]:
        num.popleft()
        innum.popleft()
        if innum:
            continue
        else:
            break

    if len(num) // 2 >= num.index(innum[0]):
        while num[0] != innum[0]:
            num.append(num.popleft())
            cnt += 1

    else:
        while num[0] != innum[0]:
            num.appendleft(num.pop())
            cnt += 1

print(cnt)

문제요약

원소를 뽑는데 3가지 연산이 있는데 2,3번 연산을 최소로 사용한 횟수를 구하라.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

설명

문제를 자세히 보면 수를 뽑는 건 앞에서만 이루어진다.

다시 말해서 1번만 수를 뽑을 수 있다.

 

이를 예시로 들었을 때

다음과 같이 2를 먼저 뽑는데 2는 조건 2번을 이용하는게 가장 빠르다 따라서 2번을 1번 사용하여 수를 뽑는다.

그다음 9는 3번을 이용해서 뽑는게 가장 최소로 이용하는 방법이다.

따라서 3번을 3번 사용하여 수를 뽑는다.

마지막으로 5는 3번을 4번 이용하면 가장 최소로 이용할 수 있다.

 

결과적으로 1 + 3 + 4 로 총 8번으로 원하는 수를 뽑을 수 있다.

 

num = deque(i for i in range(1, N+1))

 

 

먼저 1부터 N까 값을 데큐에 저장하였다.

 

 

1.첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.

    if num[0] == innum[0]:
        num.popleft()
        innum.popleft()
        if innum:
            continue
        else:
            break

만약 회전을 돌리는 데큐(num)의 맨 앞자리와 입력받은 뽑고자하는 수(innum)이 같다면 그 수를 뽑는다.

뽑고자하는 수가 남아있다면, 반복문을 계속 진행하고 그렇지 않다면 종료시킨다.

 

 

2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.

    if len(num) // 2 >= num.index(innum[0]):
        while num[0] != innum[0]:
            num.append(num.popleft())
            cnt += 1

현재 길이의 반으로 나눈 값이 뽑고자 하는 수의 위치보다 크다면 (뽑고자 하는 수가 반보다 앞에있거나 같다)

2번 조건을 진행한다.

뽑을 수가 맨 앞으로 오기까지 cnt(count)를 증가 시킨다.

 

 

3.오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

    else:
        while num[0] != innum[0]:
            num.appendleft(num.pop())
            cnt += 1

2번 조건에 해당하지 않는다면 3번이 진행되며, 3번또한 뽑고자 하는 수가 맨앞에 오기까지 cnt를 증가시킨다.