[BOJ] 18258번: 큐 2 / Python - collection의 deque로 성능 충족하기

https://www.acmicpc.net/problem/18258

최대 2,000,000개까지 입력되는 다양한 명령문에 대해, 큐 관련 동작을 수행하는 문제이다.

명령의 수가 매우 많기 때문에, 비효율적인 자료구조나 로직을 사용하면 페널티가 있을 수 있다.

 

먼저, 큐를 구현하기 위해 일반적인 list를 사용해보았다. 그러나 아래처럼 시간 초과가 발생하게 되었다.

시간 초과 발생 코드

import sys

queue = []
results = []
commands = sys.stdin.readlines()[1:]
for command in commands:
    cmd_x = command.split()
    cmd = cmd_x[0]
    if cmd == "push":
        queue.append(cmd_x[1])
    elif cmd == "pop":
        results.append(queue.pop(0) if queue else "-1")
    elif cmd == "size":
        results.append(str(len(queue)))
    elif cmd == "empty":
        results.append("0" if queue else "1")
    elif cmd == "front":
        results.append(queue[0] if queue else "-1")
    elif cmd == "back":
        results.append(queue[-1] if queue else "-1")

sys.stdout.write("\n".join(results))

시간 초과의 원인은 바로 queue.pop(0) 부분에 있다.

pop(0) 연산은 list의 첫 번째 요소를 제거할 때 O(n)의 시간 복잡도를 가지므로, 입력 데이터가 많을 경우 시간 초과가 발생할 수 있다.

List의 내부 동작 방식

파이선의 list는 동적 배열(dynamic array)로 구현되어 있다. 이는 요소들이 메모리상에 연속적으로 저장된다는 뜻이다.

pop(0)은 리스트의 맨 앞 요소를 제거한 뒤, 남은 요소들을 한 칸씩 앞으로 이동시킨다.

즉, 리스트의 길이가 n일 때,

1. 첫 번째 요소를 제거.
2. 모든 나머지 요소들을 왼쪽으로 한 칸씩 이동.

이러한 이동 과정은 요소 수에 비례하므로, 시간 복잡도가 O(n)이다.

 

List의 위와 같은 성능적 한계를 피하기 위해, collections의 deque를 사용한다.

deque는 양쪽에서의 삽입과 삭제를 O(1)로 지원하도록 설계된 자료구조이다. 내부적으로는 이중 연결 리스트로 구현되어 있기 때문에 요소 이동이 필요하지 않다. 따라서 큐를 구현할 때 deque를 사용하는 것이 성능 면에서 훨씬 효율적이다.

queue에서의 pop(0)을 대신하여, deque에서는 popleft()를 사용하면 된다.

정답 코드

import sys
from collections import deque

queue = deque()
results = []
commands = sys.stdin.readlines()[1:]

for command in commands:
    cmd_x = command.split()
    cmd = cmd_x[0]
    if cmd == "push":
        queue.append(cmd_x[1])
    elif cmd == "pop":
        results.append(queue.popleft() if queue else "-1")
    elif cmd == "size":
        results.append(str(len(queue)))
    elif cmd == "empty":
        results.append("0" if queue else "1")
    elif cmd == "front":
        results.append(queue[0] if queue else "-1")
    elif cmd == "back":
        results.append(queue[-1] if queue else "-1")

sys.stdout.write("\n".join(results))

성능이 합격 조건에 충족된 것을 확인할 수 있다.