BOJ 10845 큐 풀이

[allzeroyou]

문제 분석

첫 번째 단계(문제 요약 및 조건 파악)

정수를 저장하는 큐 구현하고, 입력으로 주어지는 명령 처리

명령은 총 6가지

• push x: 정수 x를 큐에 넣음

• pop: 큐에서 가장 앞에 있는 정수 꺼내기, 그 수를 출력. 만약 큐가 비었다면 -1 출력

• size: 큐에 들어있는 정수 개수 출력

• empty: 큐가 비어있으면 1, 아니면 0 출력

• front: 큐에서 가장 앞에 있는 정수 출력. 만약 큐가 비었다면 -1 출력

• back: 큐에서 가장 뒤에 있는 정수 출력. 만약 큐가 비었다면 -1 출력

• 입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어짐.

둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다

주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

• 출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

두 번째 단계 (문제 핵심 파악)

6가지 기능을 갖춘 큐를 구현한다

파이썬에서 제공하는 큐 자료구조인 deque를 이용하자

• 큐 구현시 list를 이용하지 않는 이유

  스택에서 list.append와 list.pop()을 이용했던 것처럼 list.append와 list.pop(0)을 이용하면 리스트를 큐처럼 사용할 수 있다. 하지만 pop()의 time complexity는 O(1)인 반면 pop(0)의 time complexity는 O(N)이기 때문에 시간이 오래 걸린다. 따라서 시간 복잡도를 고려해 리스트는 큐로 사용하지 않는다.

코드 작성

import collections
import sys

input = sys.stdin.readline

q = collections.deque()  # 큐 생성
n = int(input())

for _ in range(n):
    command = input().split()
    if command[0] == "push":  # push 명령
        q.append(command[1])
    elif command[0] == "front":
        if not q:  # 큐가 비었다면
            print(-1)
        else:
            print(q[0])
    elif command[0] == "back":
        if not q:  # 큐가 비었다면
            print(-1)
        else:
            print(q[-1])
    elif command[0] == "size":
        print(len(q))
    elif command[0] == "empty":
        if not q:  # 큐가 비었다면
            print(1)
        else:
            print(0)
    elif command[0] == "pop":
        if not q:  # 큐가 비었다면
            print(-1)
        else:
            print(q.popleft())

느낀점

deque vs heapq

deque는 스택+큐 자료구조. 가장자리의 원소를 넣거나 뺄 수 있다. pop()과 popleft() 모두 시간복잡도가 O(1)로 매우 좋다.

메서드	설명
deque(iterable, [, maxlen])	초기화 함수이다. iterable(리스트 등)을 인자로 건내면 이를 deque화 시켜준다.
append(x)	x를 덱의 오른쪽에 삽입한다.
popleft()	덱의 가장 왼쪽에 있는 원소를 덱에서 제거하고, 그 값을 리턴한다.
clear()	모든 원소를 지운다.

heapq는 우선순위 큐. 최소 힙을 지원하며, 최단 경로를 탐색하는 다익스트라 알고리즘 등에 사용됨.

• 근데 힙은 뭔데?

  • 최솟값, 최댓값을 빠르게 찾기 위해 고안된 완전 이진 트리.

  • 최솟값이나 최댓값을 찾기 위해 배열을 사용하면 Ο(n)만큼 시간이 걸린다.

    하지만 힙을 사용하면 O(logn)만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있다.

    우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야하는 알고리즘 등에 활용된다.

참고 블로그

• deque
  (https://ooeunz.tistory.com/31)

• heap
  (https://velog.io/@gnwjd309/data-structure-heap)