백준 18258번 큐2

백준 18258번 큐2 문제이다.

 

문제를 보면 

 

명령어를 계속해서 받고 명령어에 따라 큐를 처리해주면 되는 문제이다. 

코드를 짜는 것은 쉽다, 하지만 리스트로 구현을 하는 경우 O(n)의 복잡도를 갖기 때문에 시간 초과가 발생한다.

O(1)의 복잡도를 갖는다는 Queue를 사용하여 구현을 하려 했으나 어디서 큰 복잡도를 갖는것인지 시간초과가 나왔다...

결국엔 deque를 사용하여 풀었다. deque가 속도나, 사용하기에 훨씬 편한것 같다. 

 

코드는 다음과 같다. 

import sys
from collections import deque

n = int(sys.stdin.readline().strip())
deq = deque()
for i in range(n):
    ins = sys.stdin.readline().strip()
    if ins == 'pop':
        if len(deq) == 0:
            print(-1)
        else:
            print(deq.popleft())
    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, num = ins.split()
        num = int(num)
        deq.append(num)

명령어를 하나씩 차근차근 받아서 처리해주면 무난히 구현은 가능하다.

요소 입출력이 많은 경우 최고는 deque라고 생각한다.

 

성공!