백준 1021번 파이썬

문제 파악

• input: 큐 크기 N, 뽑아내는 수의 개수 M
• output: 오른쪽/왼쪽 이동하는 연산의 최솟값

풀이

뽑아내려는 수의 위치가 앞/뒤 중 어디에 더 가까운지 파악하기

• 어느 방향으로 회전하는 것이 더 최소일까?

1. 리스트

n, m = map(int, input().split())
numlist = list(map(int, input().split()))
q = [i for i in range(1, n + 1)] # 전체 큐
cnt=0 # 연산 횟수

for i in range(m):
    qlen=len(q)
    qidx=q.index(numlist[i])
    if qidx < qlen-qidx: # 왼쪽으로 회전
        while True:
            if q[0] == numlist[i]:
                del q[0]
                break
            else:
                q.append(q[0])
                del q[0]
                cnt+=1
                
    else: # 오른쪽으로 회전
        while True:
            if q[0] == numlist[i]:
                del q[0]
                break
            else:
                q.insert(0, q[-1])
                del q[-1]
                cnt +=1
print(cnt)

2. deque

deque의 rotate 함수 활용하기

import sys
from collections import deque

n, m = map(int, input().split())
numbers = list(map(int, input().split()))
q = deque(range(1, n+1))
cnt = 0

for idx in range(len(numbers)):
    if numbers[idx] == q[0]:
        q.popleft()
        continue
    q_idx = q.index(numbers[idx])
    
    if q_idx > len(q) // 2: 
        q.rotate(len(q) - q_idx) # 3번 연산
        cnt += (len(q) - q_idx)
        
    elif q_idx <= len(q) // 2: 
        q.rotate(-q_idx) # 2번 연산
        cnt += q_idx
    q.popleft()
    
print(cnt)

Memo

deque의 내장 함수들이 활용하기 좋은 것들이 많아서 더 직관적으로 코드를 구현할 수 있는 듯. deque 내장함수 목록