[BOJ 백준] - 큐2 18258 Python

7638 단어 algorithmbojalgorithm

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


문제설명
n개 명령어를 받고 그대로 실행결과를 보여주면 된다.


풀이
사실 큐라는 자료구조를 이해하고 있다면 어려움이 없는 문제이다.
그리고 파이썬에서 큐를 사용하는 것은 매우 간편하기 때문에 더 편한 문제였다.

핵심은 시간이다.
굉장히 여러번 리스트 연산을 해야 하는데 주어진 시간이 짧다 ..

가장 시간이 오래 걸리는 연산은 첫번째 (가장 앞) 원소를 빼는 것이다.
첫번째 원소를 빼면 뒤에 모든 원소들이 앞으로 당겨져야 한다.
보통 첫번째 원소를 삭제할 때 del을 많이 쓸텐데 이거는 우리가 예상한 대로 최악의 경우 리스트의 길이만큼 앞 쪽으로 당겨줘야 한다.

파이썬의 dequepopleft 라는 쩌는 메서드를 지원한다. 내부적으로 어떻게 돌아가는지 알게 뭔가 그냥 O(1)에 가까운 성능일 낸다고 한다...

import deque

dq = deque()

dq.append(1)
item = dq.popleft()

deque의 사용법은 위가 전부다 ㅎ 나머지는 리스트와 동일

추가로
시간이 고민된다면 고민하지 말고 sys.stdin.readline()을 사용하자.

📌 전체코드

import sys
from collections import deque

n = int(sys.stdin.readline())
dq = deque()

for _ in range(n):
    command = sys.stdin.readline().split()
    #command = input().split()

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

좋은 웹페이지 즐겨찾기