백준 알고리즘: 10866번 덱 (Python)

문제 정보

---

 

10866번: 덱

 

 

핵심

---

덱(Deque)의 구조와 각 명령들에 대해 알면 쉽게 풀이할 수 있는 것 같다

덱(Deque)은 "Double Ended Queue"의 약자로, 양쪽 끝에서 삽입과 삭제가 모두 가능한 선형 자료구조이다.

덱은 큐(Queue)와 스택(Stack)의 기능을 모두 갖고 있어, 큐와 스택의 동작을 유연하게 수행할 수 있다.

덱의 구조는 일렬로 나열된 항목들로 이루어진 컬렉션입니다.
각 항목은 노드(node)라고도 부르며, 이 노드들은 양방향 링크로 연결되어 있습니다.
첫 번째 노드는 "front"라고 부르고, 마지막 노드는 "rear"라고 부른다.

덱은 다음과 같은 주요한 명령들을 지원합니다:
삽입(Insertion)
- front에 항목을 추가하는 명령을 "push_front"라고 합니다.
- rear에 항목을 추가하는 명령을 "push_back"이라고 합니다.
삭제(Deletion)
- front에서 항목을 제거하는 명령을 "pop_front"라고 합니다.
- rear에서 항목을 제거하는 명령을 "pop_back"이라고 합니다.
접근(Access)
- front나 rear에 위치한 항목을 읽는 명령을 "front"와 "back"이라고 합니다.
이를 통해 해당 위치에 있는 항목을 확인할 수 있습니다.

덱은 큐의 FIFO(First-In-First-Out) 특성과 스택의 LIFO(Last-In-First-Out) 특성을 모두 가지고 있기 때문에, 양쪽 끝에서 삽입과 삭제가 가능하며, 양쪽에서 접근이 가능합니다.
이러한 특성으로 인해 다양한 상황에서 유용하게 활용될 수 있습니다.

 

풀이

---

from collections import deque
import sys

def sol():
    d = deque()
    n = int(sys.stdin.readline())
    for i in range(n):
        com = sys.stdin.readline().split()
        if com[0] == 'push_front':
            d.appendleft(com[1])
        elif com[0] == 'push_back':
            d.append(com[1])
        elif com[0] == 'pop_front':
            print(d.popleft() if d else -1)
        elif com[0] == 'pop_back':
            print(d.pop() if d else -1)
        elif com[0] == 'size':
            print(len(d))
        elif com[0] == 'empty':
            print(0 if d else 1)
        elif com[0] == 'front':
            print(d[0] if d else -1)
        elif com[0] == 'back':
            print(d[-1] if d else -1)

sol()

저번 큐나 스택 풀이와 비슷하게 그냥 단순 덱의 구조만 알고있다면 풀수 있던 문제였던 것 같다

이제 실행시간을 줄이고자, 여러 노력을 했었지만

from collections import deque
import sys

def sol():
    d = deque()
    n = int(sys.stdin.readline().strip())
    for _ in range(n):
        com = sys.stdin.readline().strip()
        if 'push_front' in com:
            d.appendleft(com[11:])
        elif 'push_back' in com:
            d.append(com[10:])
        elif 'pop_front' in com:
            print(d.popleft() if d else -1)
        elif 'pop_back' in com:
            print(d.pop() if d else -1)
        elif 'size' in com:
            print(len(d))
        elif 'empty' in com:
            print(0 if d else 1)
        elif 'front' in com:
            print(d[0] if d else -1)
        elif 'back' in com:
            print(d[-1] if d else -1)

sol()

이런식으로 문자열을 split 하지 않고 직접 문자열로 in 키워드를 사용하여 문자열에 해당 문자열이 포함되어 있는지 확인한 후에 배열의 인덱스부터 데이터를 뽑아와 push 할 수를 찾을 수 있었다

 

고찰

---

in / not in

if 'push_front' in com:

 

'push_front' 가 문자열 변수 com 에 들어있는 지 확인할 수 있다

 

if 'push_front' not in com:

만약 이 반대라면 다음과 같이 사용할 수 있다

 

strip()

strip()_ 문자열 및 공백 제거