[Python/파이썬] 백준 알고리즘 10866번 - 덱 (Stack 두 개로 덱 구현하는 방법)

 

 

 

<풀이 - Stack 두 개를 이용한 풀이>

https://kbwplace.tistory.com/87

[Python/파이썬] 백준 알고리즘 1406번 - 에디터

여기서 풀었던 방법을 응용했다.

 

문제의 시간 제한이 0.5초로 빡빡한 편이라 시간 단축을 위해서 insert와 같은 high cost의 함수는 사용하지 않고 append, pop 함수만으로 구현해야한다.

이것을 구현하는 방법은 위의 1406번 문제를 풀었던 방법을 응용해 이렇게 스택 두 개로 deque를 표현하는 것이다.

 

import sys

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

stack_1 = []    # deque 의 front
stack_2 = []    # deque 의 back
for _ in range(N):
    command = sys.stdin.readline().rstrip().split()
    if command[0] == "push_front":
        stack_1.append(command[1])
    elif command[0] == "push_back":
        stack_2.append(command[1])
    elif command[0] == "pop_front":
        if stack_1:
            print(stack_1.pop())
        else:
            if stack_2:
                print(stack_2.pop(0))
            else:
                print(-1)
    elif command[0] == "pop_back":
        if stack_2:
            print(stack_2.pop())
        else:
            if stack_1:
                print(stack_1.pop(0))
            else:
                print(-1)
    elif command[0] == "size":
        print(len(stack_1) + len(stack_2))
    elif command[0] == "empty":
        if stack_1 or stack_2:
            print(0)
        else:
            print(1)
    elif command[0] == "front":
        if stack_1:
            print(stack_1[-1])
        else:
            if stack_2:
                print(stack_2[0])
            else:
                print(-1)
    elif command[0] == "back":
        if stack_2:
            print(stack_2[-1])
        else:
            if stack_1:
                print(stack_1[0])
            else:
                print(-1)

 

 

 

<풀이 >

물론 파이썬의 내장함수 deque를 이용한 풀이도 있다.

# 파이썬 내장함수 deque을 이용한 풀이 ↓
import sys
from collections import deque

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

deq = deque()
for _ in range(N):
    command = sys.stdin.readline().rstrip().split()
    if command[0] == "push_front":
        deq.appendleft(command[1])
    elif command[0] == "push_back":
        deq.append(command[1])
    elif command[0] == "pop_front":
        if deq:
            print(deq.popleft())
        else:
            print(-1)
    elif command[0] == "pop_back":
        if deq:
            print(deq.pop())
        else:
            print(-1)
    elif command[0] == "size":
        print(len(deq))
    elif command[0] == "empty":
        if deq:
            print(0)
        else:
            print(1)
    elif command[0] == "front":
        if deq:
            print(deq[0])
        else:
            print(-1)
    elif command[0] == "back":
        if deq:
            print(deq[-1])
        else:
            print(-1)

 

하지만 처리 시간을 봤을 때 stack 두개를 이용하는 풀이가 더 빠르다.

위에 것이 deque를 이용한 풀이, 아래 것이 stack 두 개를 이용한 풀이

시간 제한이 빡빡하다면 시도해 볼만한 풀이이다.

 

 

 

<핵심 정리>

1. deque는 stack 두 개로 구현할 수도 있다.

2. 파이썬 내장함수 collections deque를 이용해 deque를 사용할 수 있다.