사실 이번 주에는 매일 2개씩 올릴 건데, 그 이유는... 저번 주에 알고리즘을 풀기만 하고 오답블로그 (?)를 적지 않았기 때문이다 ^^

10866: 덱

새로운 자료구조였다. 스택, 큐는 워낙 유명하고 많이들 아니까 그렇다고쳐도... 덱은 정말 처음 듣는 구조였다. 일단 코드를 공유하고 ~ 덱에 대해서 알아보자.

1. 내 풀이: 성공

import sys

order = int(sys.stdin.readline())
deque =[]

for _ in range(order):
    command = sys.stdin.readline().strip().split()
    if command[0]== 'push_front':
        deque.insert(0, command[1])
    elif command[0] == 'push_back':
        deque.append(command[1])
    elif command[0] == 'pop_front':
        if len(deque) == 0:
            print(-1)
        else:
            print(deque.pop(0))
    elif command[0] == 'pop_back':
        if len(deque) == 0:
            print(-1)
        else:
            print(deque.pop(-1))
    elif command[0] == 'size':
        print(len(deque))
    elif command[0] == 'empty':
        if len(deque) == 0:
            print(1)
        else:
            print(0)
    elif command[0] == 'front':
        if len(deque) != 0:
            print(deque[0])
        else:
            print(-1)
    elif command[0] == 'back':
        if len(deque) !=0:
            print(deque[-1])
        else:
            print(-1)

# insert (-1, command[1]) -> append로 바꾸니까 맞았음

아니 사실 이 문제를

보다시피 2번이나 틀렸었다. 사실 맞는데 !!! terminal에서 돌렸을 때는 문제 없었는데 boj에서는 계속 틀렸다고 해서... 뭐... 그냥 append로 고쳤다.

음, 이 문제는 일일이 풀이 방식을 설명하는 건 비효율적인 것 같다. 왜냐하면 앞서 큐랑 스택도 비슷한 로직으로 풀었으니까! 그러니 이제 덱에 대해서 알아보자.

2. 덱이란?

덱 Deque은 소위 양방향 큐라고 한다. 위아래 구멍이 뽕뽕 뚫린 파이프 모양의 자료구조이기 때문이다. 큐 역시 파이프 모양의 자료구조인데, 큐는 한 쪽 방향으로만 나가고 들어가고가 가능하다면, 덱은 양방향으로 나가고 들어가고가 가능하다.

(출처: https://soft.plusblog.co.kr/24)

이렇게 생겼다. 이전에 배운 스택, 큐 자료구조와 크게 다를 게 없기 때문에... 이정도만 설명해도 충분하지 않을까 한다.

3. 다른 풀이: Deque() 이용

다른 풀이를 찾아보다가 Deque()을 이용한 풀이가 많아서 한 번 정리해볼까 한다.
아래의 블로그를 참고했다.
(출처: https://velog.io/@tkdduf727/%EB%B0%B1%EC%A4%80-%EB%8D%B1-10866%EB%B2%88-%ED%8C%8C%EC%9D%B4%EC%8D%AC-Python-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0)

from collections import deque
import sys

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

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

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

collection module에서 Deque을 import 해준다. 전체적인 로직은 비슷하고, appendleft를 썼냐, popleft를 썼냐의 차이만 조금 다른 것 같다. 역시... 다 제공해주니까 너무 편하다 ㅎㅎㅋㅎ...

오늘도 신기한 알고리즘의 세계 끝!