[백준] 10866번: 덱 python

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

10866번: 덱

 

문제 정보

문제 유형 난이도 걸린 시간 스스로 구현 성공

덱

실버4

10m

O

 

설계 방법

내가 구현한 방법

덱 클래스 생성 후 각 메소드 구현

다른 풀이 1

간단하게 deque 모듈을 사용한 풀이

다른 풀이 2

dictionary를 이용하여 switch-case문을 구현

이를 이용하여 key값을 가지고 딕셔너리에 접근하여 대응되는 value값을 통해 함수를 호출

 

코드

내 풀이

import sys
input = sys.stdin.readline

class Deque:
  def __init__(self):
    self.data = []
  def size(self):
    return len(self.data)
  def empty(self):
    if len(self.data) == 0:
      return 1
    else:
      return 0
  def push_front(self, x):
    self.data.insert(0, x)
  def push_back(self, x):
    self.data.append(x)
  def pop_front(self):
    if len(self.data) == 0:
      return -1
    else:
      ans = self.data[0]
      self.data = self.data[1:]
      return ans
  def pop_back(self):
    if len(self.data) == 0:
      return -1
    else:
      ans = self.data[-1]
      self.data = self.data[:-1]
      return ans
  def front(self):
    if len(self.data) == 0:
      return -1
    else:
      return self.data[0]
  def back(self):
    if len(self.data) == 0:
      return -1
    else:
      return self.data[-1]

n = int(input())
deque = Deque()
for _ in range(n):
  cmd = input().split()
  op = cmd[0]
  if op == 'size':
    print(deque.size())
  elif op == 'empty':
    print(deque.empty())
  elif op == 'push_front':
    deque.push_front(cmd[1])
  elif op == 'push_back':
    deque.push_back(cmd[1])
  elif op == 'pop_front':
    print(deque.pop_front())
  elif op == 'pop_back':
    print(deque.pop_back())
  elif op == 'front':
    print(deque.front())
  elif op == 'back':
    print(deque.back())
  else:
    print('err')

 

다른 풀이 1

from collections import deque
import sys

d = deque()
n = int(input())

for i in range(n):
    cmd = sys.stdin.readline().split()

    if cmd[0] == "push_front":
        d.appendleft(cmd[1])
    elif cmd[0] == "push_back":
        d.append(cmd[1])
    elif cmd[0] == "pop_front":
        if d:
            print(d[0])    
            d.popleft()
        else:
            print("-1")
    elif cmd[0] == "pop_back":
        if d:
            print(d[len(d) - 1])
            d.pop()
        else:
            print("-1")
    elif cmd[0] == "size":
        print(len(d))
    elif cmd[0] == "empty":
        if d:
            print("0")
        else:
            print("1")
    elif cmd[0] == "front":
        if d:
            print(d[0])
        else:
            print("-1")
    elif cmd[0] == "back":
        if d:
            print(d[len(d) - 1])
        else:
            print("-1")

 

다른 풀이 2

def push_front(x, deq):
    tmp = [x]
    tmp.extend(deq)
    deq = tmp
    return deq

def push_back(x, deq):
    deq.append(x)
    return deq

def pop_front(deq):
    if deq : 
        print(deq.pop(0))
    else : #빈 리스트 == False
        print(-1)
    
def pop_back(deq):
    if deq :
        print(deq.pop())
    else :
        print(-1)

def size(deq):
    print(len(deq))

def empty(deq) :
    if not deq : 
        print(1)
    else : 
        print(0)
    
def front(deq) :
    if deq :
        print(deq[0])
    else :
        print(-1)
    
def back(deq) :
    if deq :
        print(deq[-1])
    else :
        print(-1)

statements_dict = {
    'push_front' : push_front,
    'push_back' : push_back,
    'pop_front' : pop_front,
    'pop_back' : pop_back,
    'size' : size,
    'empty' : empty, 
    'front' : front,
    'back' : back
}

N = int(input())

deq = []

for _ in range(N) :
    statement = input().split(" ")
    
    if len(statement) == 1 : 
        command = statement[0]
        statements_dict[command](deq)
    else :
        command, x = statement
        deq = statements_dict[command](x, deq)

시간 복잡도

$O(n)$

어려웠거나 새로 알게된 점

deque 모듈의 존재(appendleft, popleft 등등 ..)

dictionary로 구현하는 방법

.. 아직 python에 대해서도 배워나가야 할 게 정말 많구나 느꼈음 

배울게 너무 많아 !! 😭

참고 자료

[Algorithm] [Python] BOJ/백준 - 10866_덱