[백준 / python] 10866번 : 덱

알고리즘 분류 구현 자료구조 덱

🔗 문제 출처 https://www.acmicpc.net/problem/10866

---

이 문제는 큐의 특성을 사용해 푸는 문제이다. 파이썬에는 모듈로 deque를 지원하기 때문에 쉽게 풀 수 있다. 하지만 처음에는 컬렉션을 가져오지 않고 오로지 리스트로 풀었다. 코드는 아래와 같다.

📎 코드

python

import sys

dq = []

for _ in range(int(sys.stdin.readline())):
  command = list(sys.stdin.readline().split())
  if command[0] == 'push_front':
    dq.append(command[1])
    
  elif command[0] == 'push_back':
    dq.reverse()
    dq.append(command[1])
    dq.reverse()
    
  elif command[0] == 'pop_front':
    if dq: print(dq.pop())
    else: print(-1)

  elif command[0] == 'pop_back':
    if dq: print(dq.pop(0))
    else: print(-1)

  elif command[0] == 'size':
    print(len(dq))

  elif command[0] == 'empty':
    print(0) if len(dq) != 0 else print(1)

  elif command[0] == 'front':
    print(dq[len(dq)-1]) if len(dq) != 0 else print(-1)

  elif command[0] == 'back':
    print(dq[0]) if len(dq) != 0 else print(-1)

리스트로 구현했기 때문에 push_front(혹은 push_back)을 리스트의 함수를 통해서 구현을 해야만 했다.

back에 pop을 할 때 리스트의 맨 첫 번째 인덱스에 push를 해야하기 때문에 리스트를 뒤집은 후 append()를 하고 다시 리스트를 뒤집었다. 시간제한이 0.5초라 시간제한에 걸릴 수도 있겠다라는 생각을 했는데 다행히 문제 없었다.

하지만 이 방법보다는 더 안전한, 그리고 훨씬 편안한 deque 컬렉션을 가져와서 사용하는 것을 추천한다.

📎 코드

모듈이 import된 코드

import sys
from collections import deque

dq = deque()

for _ in range(int(sys.stdin.readline())):
  command = list(sys.stdin.readline().split())
  if command[0] == 'push_front':
    dq.append(command[1])
    
  elif command[0] == 'push_back':
    dq.appendleft(command[1])
    
  elif command[0] == 'pop_front':
    if dq: print(dq.pop())
    else: print(-1)

  elif command[0] == 'pop_back':
    if dq: print(dq.popleft())
    else: print(-1)

  elif command[0] == 'size':
    print(len(dq))

  elif command[0] == 'empty':
    print(0) if len(dq) != 0 else print(1)

  elif command[0] == 'front':
    print(dq[len(dq)-1]) if len(dq) != 0 else print(-1)

  elif command[0] == 'back':
    print(dq[0]) if len(dq) != 0 else print(-1)

다른 점을 deque의 appendleft()와 popleft()를 사용한 것이다. 이 두 함수의 시간복잡도는 O(1)이다. 특별한 이유가 아니라면 deque문제를 풀 때는 리스트를 사용하기 보다는 deque를 가져와서 사용하는 것이 효율적이고 안전할 것이다.