[정글 베이직 16] — 큐 · 프린터 대기열

📋 문제 소개

문제 설명

큐(Queue)를 사용하여 프린터 작업을 입력 순서대로 처리한다. FIFO(First In First Out) 구조를 활용한다.

INPUT

인쇄 작업 리스트 jobs (예: ["문서A", "문서B", "문서C"])

OUTPUT

작업이 처리되는 순서 (리스트)

예제

입력

jobs = ["문서A", "문서B", "문서C"]

출력

처리: 문서A 처리: 문서B 처리: 문서C

💡 힌트

파이썬에서 큐 구현 시 deque 사용. append()로 뒤에 추가, popleft()로 앞에서 제거.

① 문제 이해

항목	내용
문제	프린터 작업을 입력 순서대로(FIFO) 처리한다.
자료구조	큐 (FIFO — First In First Out)
예제	["문서A","문서B","문서C"] → 순서대로 처리

② 핵심 아이디어

리스트로 큐를 구현하면 pop(0)이 O(n)이 되어 비효율적이다. collections.deque의 popleft()는 O(1)이므로 항상 deque를 쓴다.

# list.pop(0) — O(n)  ❌
# deque.popleft() — O(1) ✅

from collections import deque
queue = deque(jobs)
while queue:
    job = queue.popleft()
    처리...

③ 코드 분석

from collections import deque

def process_print_queue(jobs):
    queue = deque(jobs)    # ① deque로 감싸기
    processed = []

    while queue:           # ② 큐가 빌 때까지
        job = queue.popleft()   # ③ O(1) — 앞에서 꺼내기
        print(f"처리: {{job}}")
        processed.append(job)

    return processed

번호	코드	의미
①	deque(jobs)	리스트를 deque로 변환 — O(n)
②	while queue	빈 deque는 falsy — 자연스러운 루프 종료 조건
③	popleft()	양방향 연결 구조라 앞 포인터만 이동 → O(1)

④ list.pop(0) vs deque.popleft()

방법	시간복잡도	이유
list.pop(0)	O(n)	앞 원소 제거 후 나머지를 전부 한 칸씩 앞으로 이동
deque.popleft()	O(1)	양방향 연결리스트 — 앞 포인터만 이동하면 끝

💡 큐가 필요하면 항상 from collections import deque. 파이썬 리스트로 큐를 흉내 내면 성능이 선형으로 나빠진다.

⑤ 시간복잡도

항목	값	이유
시간	O(n)	n개 작업을 각 O(1)에 처리
공간	O(n)	deque에 n개 원소 저장

⑥ 핵심 정리

• 큐 = FIFO. 먼저 들어온 것이 먼저 나간다.
• 파이썬에서 큐 → from collections import deque, popleft().
• list.pop(0) 은 O(n) — 절대 쓰지 말자.