[Python] 백준 1021 회전하는 큐

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

1021번: 회전하는 큐

 

문제

 

 

해설

 

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

 

1. 첫 번째 원소를 뽑아낸다.

• 1, 2, 3, 4, 5, 6, 7, 8, 9 중에서 1을 뽑고자 1번 연산을 수행하면 → 2, 3, 4, 5, 6, 7, 8, 9

2. 왼쪽으로 한 칸 이동시킨다.

• 2, 3, 4, 5, 6, 7, 8, 9에서 4가 뽑고 싶은 경우
• 3, 4, 5, 6, 7, 8, 9, 2 (2번 연산 1번 수행)
• 4, 5, 6, 7, 8, 9, 2, 3 (2번 연산 2번 수행)→ 4를 뽑음

3. 오른쪽으로 한 칸 이동시킨다.

• 5, 6, 7, 8, 9, 2, 3 에서 2가 뽑고 싶은 경우
• 3, 5, 6, 7, 8, 9, 2 (3번 연산 1번 수행)
• 2, 3, 5, 6, 7, 8, 9 (3번 연산 2번 수행) → 2를 뽑음

 

+ ) 2번, 3번 연산의 최솟값을 출력하며 1번 연산은 따지지 않음

 

 

코드

 

• 양쪽에서 무언가 연산이 수행되는 것을 보아 덱 deque 을 사용해야한다
• 심지어 문제 첫째 줄에 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다 라고 적혀있음!

n, m = map(int, input().split()) 
pick = list(map(int, input().split()))
dq = deque([i for i in range(1, n+1)])
count = 0

for i in pick:
    while True:
        if dq[0] == i:
            dq.popleft() # 찾고자 하는 원소가 발견되면 왼쪽 원소 pop!
            break
        else: 
            if dq.index(i) < len(dq)/2: # 2, 3번 연산의 여부를 따지기 위해.. 가까운쪽을 찾아야함
                while dq[0] != i:
                    dq.append(dq.popleft()) 
                    count += 1
            else:
                while dq[0] != i:
                    dq.appendleft(dq.pop()) 
                    count += 1

print(count)