[백준/파이썬] 18258번

백준 18258번

문제

https://www.acmicpc.net/problem/18258

코드

#시간초과 코드
import sys

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

queue = []

for _ in range(num):
    command = sys.stdin.readline().split()

    if command[0] == 'push':
        queue.append(command[1])
        
    elif command[0] == 'pop':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue.pop(0))
    
    elif command[0] == 'size':
        print(len(queue))
        
    elif command[0] == 'empty':
        if len(queue) == 0:
            print(1)
        else:
            print(0)

    elif command[0] == 'front':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[0])

    elif command[0] == 'back':
        if len(queue) == 0 :
            print(-1)
        else:
            print(queue[-1])

#정상코드
import sys
from collections import deque
num = int(sys.stdin.readline())

queue = deque([])

for _ in range(num):
    command = sys.stdin.readline().split()

    if command[0] == 'push':
        queue.append(command[1])
        
    elif command[0] == 'pop':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue.popleft())
    
    elif command[0] == 'size':
        print(len(queue))
        
    elif command[0] == 'empty':
        if len(queue) == 0:
            print(1)
        else:
            print(0)

    elif command[0] == 'front':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[0])

    elif command[0] == 'back':
        if len(queue) == 0 :
            print(-1)
        else:
            print(queue[-1])

풀이

시간초과 코드와 정상 출력 코드와의 차이는 바로 deque를 사용했나/하지않았나의 차이.

알게된 점

- deque
양방향에서 원소를 추가하거나 삭제가 가능합니다.
즉, 스택 및 큐를 구현할 수 있습니다.
일반적인 리스트는 이러한 연산에 O(n)이 소요되는 데 반해, deque 는 O(1)로 접근 가능하다. => 즉 시간초과가 안뜬 것!