[18258] 큐 2 (Python)

BFS와 DFS 개념을 공부하고 문제를 풀어보기 위해 백준 18258번 문제를 풀어보았다.

해당 문제의 설명은 다음과 같다. 역시 시간초과를 해결하느라 머리를 굴려야했다 :)

큐의 개념을 익히고 실습하는 문제. 연산 당 시간 복잡도가 O(1)이어야 한다는 점에 유의하세요.

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

18258번: 큐 2

 

생각정리

- 큐 문제이므로 deque를 사용해야겠다! 시간복잡도가 더 적으니까~

- 사실 이거말고는 딱히 없었다.

- 처음에는 각각 함수로 만들고 input()으로 입력을 받았는데

- 시간초과가 계속 떠서 수정하고 수정하고 한 코드가 아래의 코드!

- 함수로 따로 만들어주는게 시간복잡도에 영향을 미친다고 한다. 함수로 생성해보니 런타임 에러가 떠서 함수 생성 대신 조건문의 실행문에 바로 적었다.

# 시간을 단축시키기위해서는 input()보다는 sys.stdin.readline() 추천
import sys
from collections import deque
queue = deque()

n = int(input())
for i in range(n):
    ask = sys.stdin.readline().split()  # readline은 띄어쓰기와 \n까지 포함하기 때문에 split()을 함께 써주는게 좋음!
    if ask[0].startswith('push'):
        num = int(ask[1])
        queue.append(num)
    elif ask[0] == 'pop':
        if queue:
            print(queue.popleft())
        else:
            print(-1)
    elif (ask[0] == 'size'):
        print(len(queue))
    elif (ask[0] == 'empty'):
        if queue:
            print(0)
        else:
            print(1)
    elif (ask[0] == 'front'):
        if queue:
            print(queue[0])
        else:
            print(-1)
    elif (ask[0] == 'back'):
        if queue:
            print(queue[-1])
        else:
            print(-1)