본문 바로가기

Algorithm & SQL/Baekjoon

[Algorithm] [Python] BOJ/백준 - 10866_덱

10866 - 덱


INDEX


1. 문제 설명

2. 제출 코드

3. 코드 설명

4. 다른 사람의풀이

문제


정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

push_front X: 정수 X를 덱의 앞에 넣는다.
push_back X: 정수 X를 덱의 뒤에 넣는다.
pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 덱에 들어있는 정수의 개수를 출력한다.
empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력


첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력


출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력


15
push_back 1
push_front 2
front
back
size
empty
pop_front
pop_back
pop_front
size
empty
pop_back
push_front 3
empty
front

예제 출력

2
1
2
0
2
1
-1
0
1
-1
0
3

제출 코드


from collections import deque
import sys


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

dq = deque()

def empty():
    if len(dq) == 0:
        return 1
    else:
        return 0

def size():
    return len(dq)


for i in range(N):
    cmd = list(sys.stdin.readline().split())

    if cmd[0] == 'push_front':
        dq.appendleft(cmd[1])

    elif cmd[0] == 'push_back':
        dq.append(cmd[1])

    elif cmd[0] == 'pop_front':
        if empty() == 1:
            print("-1")
        else:
            tmp = dq.popleft()
            print(tmp)

    elif cmd[0] == 'pop_back':
        if empty() == 1:
            print("-1")
        else:
            tmp = dq.pop()
            print(tmp)

    elif cmd[0] == 'front':
        if empty() == 1:
            print("-1")
        else:
            print(dq[0])

    elif cmd[0] == 'back':
        if empty() == 1:
            print("-1")
        else:
            print(dq[len(dq)-1])

    elif cmd[0] == 'size':
        print(size())

    elif cmd[0] == 'empty':
        print(empty())

코드 설명


사실 이 문제는 딱히 설명할 알고리즘은 없다.

그냥 "deque 모듈의 사용법을 아는가?" 를 묻는 문제였으므로 정말 deque의 기본 기능만 사용할 줄 안다면 쉽게 풀어낼 수 있는 문제였다.

파이썬에서는 조건에 따른 분기를 쉽게 처리할 수 있는 switch - case 구문을 지원하지 않기 때문에 다소 가독성이 좋지 못하다.

다른 분께서 본 문제를 풀고 올리신 풀이를 보다보니 dict 자료형을 이용하여 switch - case 를 직접 구현하신 분이 계셔서 해당 풀이법을 참고로 올린다.

다른 사람의 풀이

from collections import deque
import sys

def push_front(x, deq):
    tmp = [x]
    tmp.extend(deq)
    deq = tmp
    return deq

def push_back(x, deq):
    deq.append(x)

def pop_front(deq):
    if deq:
        print(deq.popleft())
    else:   # 빈 덱일 경우
        print(-1)

def pop_back(deq):
    if deq:
        print(deq.pop())
    else:
        print(-1)

def size(deq):
    print(len(deq))

def empty(deq):
    if not deq:
        print(1)
    else:
        print(0)

def front(deq):
    if deq:
        print(deq[0])
    else:
        print(-1)

def back(deq):
    if deq:
        print(deq[-1])
    else:
        print(-1)

statements_dict = {
    'push_front' : push_front,
    'push_back' : push_back,
    'pop_front' : pop_front,
    'pop_back' : pop_back,
    'size' : size,
    'empty' : empty, 
    'front' : front,
    'back' : back
}

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

deq = deque()

for _ in range(N):
    statement = input().split(" ")

    if len(statement) == 1:
        cmd = statement[0]
        statements_dict[command] (deq)
    else:
        cmd ,x = statement
        deq = statements_dict[command](x, deq)

cf) 참고 블로그

위 코드에서 배울점이 많다.

첫번째로, Dictionary 를 이용하여 switch - case 문을 구현하셨고

두번째로, 이를 이용해서 key값을 가지고 딕셔너리에 접근하여 대응되는 value값을 통해 함수를 호출하셨다. ( 이게 되는건지도 처음 알았다..! 매우 신기)

위 두개 개념은 진짜 PS 문제 푸는데도 큰 도움이 될 것 같다!