[python] 백준 10845번

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

문제 : 큐

제한

• 시간 제한 : 0.5초
• 메모리 제한 : 256MB

풀이

import sys
from collections import deque

queue = deque()

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

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

풀이 해설

• list
  list 객체의 append, pop(0) or insert(0, x), pop()를 사용하면 큐 자료 구조로 사용가능
  list는 큐 자료 구조의 효과를 내기에는 성능적으로 불리한 방법
  pop, insert는 모든 데이터를 앞/뒤로 shift해야 되기 때문에 시간 복잡도는 O(n)을 가지고 이는 데이터의 개수가 많아질수록 성능이 떨어짐을 의미한다.

• Queue
  queue 모듈의 Queue클래스
  시간복잡도 : O(1)
  list, deque와 달리 방향성이 없어 데이터 추가와 삭제가 하나의 메서드로 처리, 추가/삭제 : put(x), get()
  인덱스로 데이터에 접근하는 것을 기본적으로 지원하지 않아 위 문제에서 사용하지 않음

• deque(double-ended queue)
  데이터를 양방향에서 추가하고 제거할 수 있는 자료 구조
  popleft(), appendleft()를 사용하여 양방향에서 데이터 처리가 가능
  시간복잡도 : O(1)
  단점 : 인덱스로 데이터에 접근할 때 내부적으로 linked list를 사용하기 때문에 시간복잡도 O(n)을 가진다.

위 문제의 시간 제한과 인덱스로 데이터에 접근해야 하기 때문에 deque를 사용해 문제 해결

참조링크