[백준] 1021번 회전하는 큐(파이썬)

문제

1021번: 회전하는 큐

 

예제
10 3
2 9 5
출력
8

이 경우 아래와 같이 변화하는 하며, 돌아가는 순서를 출력해주는 문제이다.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] → [ 3, 4, 5, 6, 7, 8, 9, 10, 1]
→ [1, 3, 4, 5, 6, 7, 8, 9, 10] → [10, 1, 3,  4, 5, 6, 7, 8, 9] → [10, 1, 3,  4, 5, 6, 7, 8]....

코드

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

n, m = map(int, input().split())
li = deque([])

for _ in range(1, n + 1):
    li.append(_)

nums = list(map(int, input().split()))

cnt = 0
for num in nums:
    while True:
        if num == li[0]:
            li.popleft()
            break
        else:
            if li.index(num) > len(li) // 2:
                li.appendleft(li.pop())
                cnt += 1
            else:
                li.append(li.popleft())
                cnt += 1

print(cnt)

해설

문제 제목과 같이 덱을 사용했다. (찾아보니 .rotate()를 사용하는 방법도 있다고 한다.)

li에 n이 들어가도록 1부터 넣어줬다.

nums을 반복하는 for에 while을 넣어서 li[0]와 같아진다면 popleft와 동시에 break를 하게 해주었다.

돌아가는 부분에선 index를 생각했으나 시간 복잡도 PTSD로 다른 방식으로 풀려고 해봤으나, 너무 복잡하기도 하고 문제의 시간이 2초로 넉넉한 편이라서 사용했다.

만약 마지막 예제만 답이 16이 나온다면 index 비교하는 부분에서 => 혹은 =<을 사용했을 것이다. =부분을 빼준다면 정상적으로 작동한다.