[백준 10866번] 덱 – 덱 자료구조 구현

문제 링크: https://www.acmicpc.net/problem/10866
분류: 자료구조, 덱, 구현
난이도: 실버 4

문재 개요

정수를 저장하는 덱(Deque) 을 구현하고 다음 명령들을 처리하는 문제입니다.

 

입력 예시:

15
push_back 1
push_front 2
front
back

 

출력 예시:

2
1
2
0
2

 

문재 해석

덱이란?

─ Deque (Double-Ended Queue): 양쪽 끝에서 삽입과 삭제가 가능한 큐입니다.

• push_front, push_back : 앞/뒤로 원소 삽입
• pop_front, pop_back : 앞/뒤에서 원소 제거
• size, empty : 현재 덱 크기 및 비었는지 확인
• front, back : 양쪽 끝의 값을 확인 (단, 삭제하지 않음)

 

문제 접근 방식

• 단순한 list 사용은 pop(0) 등에서 O(n) 발생 → 비효율적
• Python의 collections.deque는 덱을 위한 최적화 자료구조
  • append, appendleft, pop, popleft 모두 O(1)
• collections.deque 활용
• sys.stdin.readline() 으로 빠른 입력 처리
• 조건별로 명령 수행 후 결과 출력

 

코드 구현 

# 덱(Deque)을 효율적으로 사용하기 위해 collections의 deque 사용
from collections import deque

# 입력이 많기 때문에 input() 대신 sys.stdin.readline() 사용 (속도 향상)
import sys
input = sys.stdin.readline

# 명령의 개수 n 입력 받기
n = int(input())

# 덱 생성: 정수를 저장할 이중 연결 리스트 구조
dq = deque()

# 명령 n개를 한 줄씩 처리
for _ in range(n):
    # 명령어를 읽고 공백 기준으로 분할 (push_front 1 -> ['push_front', '1'])
    cmd = input().strip().split()

    if cmd[0] == 'push_front':
        # 앞쪽에 정수 삽입 → appendleft()
        dq.appendleft(int(cmd[1]))

    elif cmd[0] == 'push_back':
        # 뒤쪽에 정수 삽입 → append()
        dq.append(int(cmd[1]))

    elif cmd[0] == 'pop_front':
        # 앞쪽에서 정수 제거 후 출력. 비어 있으면 -1 출력
        print(dq.popleft() if dq else -1)

    elif cmd[0] == 'pop_back':
        # 뒤쪽에서 정수 제거 후 출력. 비어 있으면 -1 출력
        print(dq.pop() if dq else -1)

    elif cmd[0] == 'size':
        # 현재 덱에 저장된 정수 개수 출력
        print(len(dq))

    elif cmd[0] == 'empty':
        # 덱이 비어있으면 1, 아니면 0 출력
        print(0 if dq else 1)

    elif cmd[0] == 'front':
        # 맨 앞 정수 출력. 비어있으면 -1 출력
        print(dq[0] if dq else -1)

    elif cmd[0] == 'back':
        # 맨 뒤 정수 출력. 비어있으면 -1 출력
        print(dq[-1] if dq else -1)

 

위 코드의 시간복잡도는 

연산	시간복잡도
push_front, push_back	O(1)
pop_front, pop_back	O(1)
size, empty, front, back	O(1)

─ 총 연산 수는 최대 10,000회 → 모두 O(1) 처리 → 시간 초과 없음

 

예외 처리 포인트

• 덱이 비어있을 때 pop/front/back은 -1을 출력해야 함
• 입력이 많기 때문에 반드시 input( ) 대신 sys.stdin.readline( ) 사용