[BOJ][Python]백준 10866 풀이

그냥 듀크입니다. 이번에는 deque(덱 또는 데크) 자료형으로 풀어보겠습니다(list로 해도 괜찮을 것 같기는 한데 추가시간이 없다는 코멘트가 있어서 처음부터 deque로 풀어봤습니다).

 

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

10866번: 덱

코드 : 

from collections import deque
import sys
ssr = sys.stdin.readline

list = deque()
n = int(ssr())
for i in range(n):
    command = ssr().rstrip()
    if command.find('push_front') != -1:
        list.appendleft(int(command[10:]))
    elif command.find('push_back') != -1:
        list.append(int(command[9:]))
    elif command == 'pop_front':
        if len(list) == 0:
            print(-1)
        else:
            print(list.popleft())
    elif command == 'pop_back':
        if len(list) == 0:
            print(-1)
        else:
            print(list.pop())
    elif command == 'size':
        print(len(list))
    elif command == 'empty':
        if len(list) == 0:
            print(1)
        else:
            print(0)
    elif command == 'back':
        if len(list) == 0:
            print(-1)
        else:
            print(list[len(list)-1])
    elif command == 'front':
        if len(list) == 0:
            print(-1)
        else:
            print(list[0])

deque은 double-ended queue의 줄임말로 장점이자 단점인 queue의 선입선출이 어떻게 보면 보완된 형태의 양방향에서 자료의 입출력이 가능한 자료형입니다. 위에서 list를 사용하지 않고 collections 모듈을 불러와 deque를 사용한다고 설명을 드렸는데요. deque는 컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우, 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, 데크(deque)는 O(1)로 접근 가능합니다(이제는 몇 번이나 말씀드린 시간복잡도에 대한 개념이므로 넘어가겠습니다). 이 때문에 제가 굳이 list로 시도하지 않고 바로 deque로 푼 것인데요. 아마 해당 문제의 테스트케이스에서 입력을 엄청나게 많이 준다면 시간제한에 걸릴 우려가 있기 때문입니다(또한 deque에서 이미 있는 appendleft나 popleft를 쓰기 위함이기도 하구요).

 

저는 예전에 차선인식을 진행하면서 아두이노와 시리얼통신을 하기 위해 데크를 썼던 기억이 납니다. 그 때 당시에는 처음 써보기도 하고 잘 몰랐기 때문에 인터넷을 뒤져가며 어떻게 쓰는지만 공부한 다음 바로 넘어갔었는데요. 언제 한 번 자료형들에 대해서도 심도있게 다뤄보겠습니다.

 

그냥 듀크였습니다.