[백준] 회전하는 큐 1021번 - Python

[백준] 회전하는 큐 1021번

나의 풀이

from collections import *
N, M = map(int, input().split())
nums = deque([i for i in range(1, N + 1)])
pick_nums = list(map(int, input().split()))
count = 0
for pick_num in pick_nums:
    if nums[0] == pick_num:
        nums.popleft()
        continue
    index, half_index = nums.index(pick_num), 0

    if len(nums) % 2 == 0:
        half_index = len(nums) // 2 - 1
    else:
        half_index = len(nums) // 2

    if index > half_index:
        while nums[0] != pick_num:
            nums.appendleft(nums.pop())
            count += 1
    else:
        while nums[0] != pick_num:
            nums.append(nums.popleft())
            count += 1
    nums.popleft()
print(count)

• 만약 뽑아야할 수가 큐의 첫번째 요소와 같다면 큐를 좌, 우로 움직일 필요가 없으므로 nums의 첫 번째 원소를 바로 빼주고 continue 를 통해 다음 연산을 진행한다.
• 같지 않다면 움직여 줘야 한다.
• 우선 뽑아야할 숫자가 현재 큐에서 몇번째 인덱스에 있는지 알아야 한다. 그렇기 때문에 index 메소드를 사용해서 인덱스를 추출해준다.
• 인덱스가 큐의 중간보다 크다면 오른쪽으로, 작다면 왼쪽으로, 같다면 좌우 상관없이 움직여 줘야 한다.
• 하지만 큐가 짝수이거나 홀수일 때를 주의해야 한다. 컴퓨터는 인덱스를 0부터 세기 때문에 짝수일 경우는 큐의 사이즈를 2로 나눌 경우 중간 값을 넘어가기 때문이다. 따라서 큐의 사이즈가 짝수라면 2로 나눈 값에서 -1을 해주고, 홀수라면 그냥 2로 나눠준 값을 중간 인덱스 값으로 활용한다.
• 만약 뽑아야할 숫자의 인덱스가(index) 중간 인덱스(half_index) 보다 크다면, 큐의 첫번째 원소가 뽑아야 할 숫자(pick_num)과 같아질 때까지 오른쪽으로 이동시켜주고, 카운트를 1씩 증가시킨다.
• 반대로 중간 인덱스보다 작거나 같으면 똑같이 pick_num과 같아질 때까지 왼쪽으로 이동시켜주고, 카운트를 1씩 증가시킨다.
• 이동이 모두 끝난 후에는 큐에서 해당 원소를 제거해준다.