🚶‍♂️Road to 코테(6) - 덱

본 게시물은 BaaarkingDog님의 실전 알고리즘 강의를 통해 공부한 것을 정리합니다.

[추가] 용감하게 시작하는 코딩테스트

[추가] 코딩 테스트 합격자 되기 - 파이썬

[추가] 좌충우돌, 파이썬으로 자료구조 구현하기

덱

양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조로. Double Ended Queue라는 뜻을 가지고 있다.

성질

• 원소의 추가가 O(1)
• 원소의 제거가 O(1)
• 제일 앞/뒤의 원소 확인이 O(1)
• 제일 상단이 아닌 나머지 원소들의 확인 및 변경이 원칙적 불가능.
  head와 rear을 queue처럼 가지고 있다.

직접 구현하는 방법도 있지만, 파이썬은 dequeue을 collections 모듈을 통해 클래스로 제공.

from collections import deque

deque 메서드

• append(item): item을 덱의 오른쪽에 삽입
• appendleft(item): Item을 덱의 왼쪽에 삽입
• pop(): 덱의 오른쪽 끝 요소를 반환하는 동시에 덱에서 제거
• popleft(): 덱의 왼쪽 끝 요소를 반환하는 동시에 덱에서 제거
• extend(list): 배열(list)을 순환하면서 덱의 오른쪽에 삽입
• extendleft(list): 배열(list)을 순환하면서 덱의 왼쪽에 추가
• remove(item): item을 덱에서 찾아 제거
• rotate(n): 덱의 n만큼 회전(양수일 경우 오른쪽, 음수일 경우 왼쪽)
  

바로 연습문제 풀어보자

연습문제 - 백준 10866

from collections import deque
import sys


def push_front(d,item):
  d.appendleft(item)
    
def push_back(d,item):
  d.append(item)
    
def pop_front(d):
  if len(d) !=0:
    temp=d.popleft()
    print(temp)
  else:
    print(-1)
  
def pop_back(d):
  if len(d) !=0:
    temp=d.pop()
    print(temp)
  else:
    print(-1)

def back(d):
  if len(d) !=0:
    temp=d[-1]
    print(temp)
  else:
    print(-1)

def size(d):
  print(len(d))
    
def front(d):
  if len(d) !=0:
    temp=d[0]
    print(temp)
  else:
    print(-1)

def empty(d):
  if len(d) !=0:
    print(0)
  else:
    print(1)


d=deque()
N=int(sys.stdin.readline())

for _ in range(N):
  a=sys.stdin.readline().split()
  if a[0]=='push_front':
    push_front(d,int(a[1]))
  elif a[0]=='push_back':
    push_back(d,int(a[1]))
  elif a[0]=='pop_front':
    pop_front(d)
  elif a[0]=='pop_back':
    pop_back(d)
  elif a[0]=='back':
    back(d)
  elif a[0]=='size':
    size(d)
  elif a[0]=='empty':
    empty(d)
  elif a[0]=='front':
    front(d)

다양한 메소드를 사용하는 것이 주요하다.