백준 1021번 파이썬

www.acmicpc.net/problem/1021

1021번: 회전하는 큐

이 문제는 index만 쓰면 금방 해결할 수 있다. 

 

처음에는 그냥 큐의 가장 앞 원소(q[0])와 비교해서 해결하도록 코드를 짰더니 최소값이 아니라 최대값에 가까운 값을 계산하고 있다는 걸 알게 되었다. 그래서 어떻게 해결하면 좋을까, 고민하다가 pop하고자 하는 숫자의 앞과 뒤의 길이를 비교해 짧은 쪽으로 연산(두번째 or 세번째)을 하면 금방 해결된다는 걸 알았다.

 

index 함수는 시간복잡도가 O(1)이기 때문에 괜히 걱정할 필요 없다!

 

<결과 코드>

from sys import stdin
from collections import deque

def firstFunc():
    q.popleft()

def secondFunc(second):
    q.append(q.popleft())
    return second + 1

def thirdFunc(third):
    q.appendleft(q.pop())
    return third + 1


q = deque()
N, M = map(int, stdin.readline().split())
wantToPop=list(map(int, stdin.readline().split()))
for i in range(1,N+1): q.append(i)

second = 0
third = 0

for number in wantToPop:
    while number != q[0]:
        if q.index(number) <= len(q)//2:
            second = secondFunc(second)
        elif q.index(number) > len(q)//2:
            third = thirdFunc(third)
    if number == q[0]: firstFunc()

print(second + third)