Deque

덱에 관한 기초적인 알고리즘 두 가지를 풀어보았다.

from collections import deque
import sys


n = int(sys.stdin.readline())
x = deque()

for _ in range(n):
    command = list(sys.stdin.readline().split())
    if command[0] == "push_front":
        x.appendleft(int(command[1]))
    elif command[0] == "push_back":
        x.append(int(command[1]))
    elif command[0] == "pop_front":
        print(len(x) == 0 and -1 or x.popleft())
    elif command[0] == "pop_back":
        print(len(x) == 0 and -1 or x.pop())
    elif command[0] == "size":
        print(len(x))
    elif command[0] == "empty":
        print(len(x) == 0 and 1 or 0)
    elif command[0] == "front":
        print(len(x) == 0 and -1 or list(x)[0])
    elif command[0] == "back":
        print(len(x) == 0 and -1 or list(x)[len(x) - 1])

다른 자료구조였으면 상당히 애를 먹었겠지만 덱은 이런 다양한 입출력을 지원하기 때문에 난이도가 낮은 활용 문제였다. 다만 분기를 많이 해야해서 수준에 비해서 오래 걸린다.
시간 제한이 0.5초 밖에 되지 않아서 pypy를 이용해서 문제를 제출했으나 시간초과... 파이썬으로 제출해도 시간초과가 나타났다.
혹시나싶어 input을 readline으로 변경해주니까 아슬아슬(?)하게 통과했다. 역시 파이썬을 좋아하지만 속도 이슈는 어떻게 못하나 보다.

---

회전하는 큐

두 번째 문제 역시 쉽지만 어느 정도 생각이라는 것을 해야하는 문제다.
위에 문제와 다르게 2초의 여유시간이 있었고 입력의 양도 적절했기 때문에 input을 사용해도 시간초과가 되지는 않는다.

from collections import deque

n, m = map(int, input().split())
to_pop = list(map(int, input().split()))
a = deque(range(1, n + 1))

answer = 0
for i in range(m):
    pop_index = a.index(to_pop[i])
    length = len(a)
    if pop_index == 0:
        a.popleft()
    elif length // 2 >= pop_index:
        a.rotate(-pop_index)
        answer += abs(-pop_index)
        a.popleft()
    else:
        a.rotate(length - pop_index)
        answer += abs(length - pop_index)
        a.popleft()
print(answer)

파이썬의 장점은 대부분의 기능이 존재한다는 점이다. rotate에 정수의 파라미터를 주게 되면 덱이 회전한다. 인덱스를 찾아서 위치가 전체 길이의 절반보다 작으면 시계 반대방향으로 크다면 시계 방향으로 회전을 하고 이동의 절대값을 더해주었다.