백준 10866번 덱

백준 10866번 덱 문제이다.

덱은 큐가 한쪽으로 들어와 반대쪽으로 나가는 것과 다르게 양쪽으로 자유롭게 들어오고 나가고 가능한 구조이다.

 

문제를 보면 

 

총 몇번의 명령을 할지 입력 받고 명령에 따라 수행하면 될 것으로 보인다. 

push 명령의 경우에는 뒤에 숫자를 따로 받기 때문에 각 명령어에 따라 처리를 다르게 해 주면 될것으로 보인다.

 

해결한 코드는 다음과 같다. 

import sys
cycle = int(input())
deq = []
for i in range(cycle):
    ins = sys.stdin.readline().strip()
    if ins == 'pop_front':
        if len(deq) == 0:
            print(-1)
        else:
            print(deq[0])
            del deq[0]
    elif ins == 'pop_back':
        if len(deq) == 0:
            print(-1)
        else:
            print(deq[len(deq)-1])
            del deq[len(deq)-1]
    elif ins == 'size':
        print(len(deq))
    elif ins == 'empty':
        if len(deq) == 0:
            print(1)
        else:
            print(0)
    elif ins == 'front':
        if len(deq) == 0:
            print(-1)
        else:
            print(deq[0])
    elif ins == 'back':
        if len(deq) == 0:
            print(-1)
        else:
            print(deq[len(deq)-1])
    else:
        ins, n = ins.split()
        n = int(n)
        if ins == 'push_front':
            deq.insert(0, n)
        else:
            deq.append(n)

덱은 리스트를 사용해서 앞 뒤로 추가, 삭제등을 사용하여 구현해 주었다.

0번째 자리에 추가해주는 insert 함수, 0번째 자리를 삭제하는 del 등을 사용하면 쉽게 구현이 가능하다. 

덱에 요소가 없다면 -1을 출력하는 예외처리도 신경써서 해줘야 한다. 

 

 

시간초과가 나서 if else만 있으면 시간복잡도가 높지 않은데 왜 초과가 나지? 했는데

검색해보니 input()을 사용하여 입력을 받으면 시간 초과가 난다고 한다. sys.stdin.readline()을 사용해주도록 하자.

그리고 sys.stdin.readline()으로 입력을 받으면 끝에 개행문자까지 입력이 들어오기 때문에 여기서는 strip()를 사용하여 처리해주었다.

 

성공!