[python] 백준 10866번 덱

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

10866번: 덱

 

 

 

 

 

💻 코드

 

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
deque_list = deque()

for i in range(n):
    tmp = input().rstrip().split()
    if len(tmp) == 1:
        command = tmp[0]
        if command == 'pop_front':
            if deque_list:
                print(deque_list.popleft())
            else:
                print(-1)
        elif command == 'pop_back':
            if deque_list:
                print(deque_list.pop())
            else:
                print(-1)
        elif command == 'size':
            print(len(deque_list))
        elif command == 'empty':
            if not deque_list:
                print(1)
            else:
                print(0)
        elif command == 'front':
            if deque_list:
                print(deque_list[0])
            else:
                print(-1)
        else:
            if deque_list:
                print(deque_list[-1])
            else:
                print(-1)
    else:
        command, x = tmp[0], tmp[1]
        if command == 'push_front':
            deque_list.appendleft(x)
        else:
            deque_list.append(x)

 

 

📝 풀이

 

덱(deque)에 대한 가장 대표적인 문제이다.

 

 

덱(Deque)이란?

스택(stack) + 큐(Queue)의 기능을 가진 양방향 큐

 

스택처럼 사용할 수도 있고, 큐처럼 사용할 수도 있다.

 

 

덱(Deque)을 사용하는 이유?

 

리스트(list)보다 속도가 훨씬 빠르기 때문이다. 가장 앞에 있는 값을 넣고 빼거나 가장 뒤에 있는 값을 넣고 빼는 데 최적화된 연산 속도를 제공하여 push, pop 연산이 자주 일어나는 알고리즘에서 장점을 부각할 수 있다.

 

알고리즘 성능 면에서 덱(Deque)이 리스트(list)보다 우세하다!

 

 

덱(Deque) 사용법

 

from collections import deque

deque_list = deque()

 

deque 모듈을 import한 뒤에 deque 리스트를 만들어주면 deque 메서드를 사용할 수 있게 된다.

 

deque 메서드 종류는 다음과 같다.

 

• deque.append(item) : 오른쪽 끝에 삽입
• deque.appendleft(item) : 왼쪽 끝에 삽입
• deque.pop() : 가장 오른쪽 요소 반환 및 삭제
• deque.popleft() : 가장 왼쪽 요소 반환 및 삭제
• deque.extend(array) : 주어진 array 배열을 순환하며 deque의 오른쪽에 추가
• deque.extendleft(array) : 주어진 array 배열을 순환하며 deque의 왼쪽에 추가
• deque.remove(item) : item을 deque에서 찾아 삭제
• deque.rotate(num) : num만큼 회전(양수면 시계 방향, 음수면 반시계 방향)

---

이 문제는 deque를 만들고, for문으로 n만큼 입력을 받으면서 각 명령어마다 if문을 이용하여 코드를 작성하면 쉽게 해결할 수 있다. 각 명령어에 대한 코드는 위의 함수를 참고하여 작성하면 된다.

 

 

※ if deque_list:

deque_list에 요소가 있으면 True를 반환하여 if문을 성립하고, 아무것도 없으면 False를 반환하여 if문이 성립하지 않도록 하는 코드이다.