프로그래머스 자율주행스쿨
TIL 20.12.04 - inf, PriorityQueue 클래스
donie
2020. 12. 5. 15:18
1. 파이썬 임의의 가장 큰 수
파이썬이 제공하는 infinite. 어떤 숫자와 비교해도 가장 크다고 판정된다.
최솟값을 찾을 때 초기값으로 이용하기 좋다.
음수를 붙일 수도 있다.
임의의 가장 큰 값 : float('inf')
임의의 가장 작은 값 : float('-inf')
2. 우선순위 큐 (Priority Queue) 클래스
1) 클래스 임포트
파이썬에서는 queue모듈에서 큐(Queue), 우선순위큐(PriorityQueue), 스택(LifoQueue)을 제공하고 있다.
from queue import PriorityQueue
2) 우선순위 큐 생성
pq = PriorityQueue(maxsize)
maxsize의 default값은 무한대이다.
특정 최대 크기를 가진 priority queue가 필요하다면 maxsize = size로 넘기면 된다.
3) 우선순위 큐 원소 추가
pq.put(element)
시간복잡도는 O(log N)이다.
4) 우선순위 큐 원소 삭제
우선순위 큐 내의 가장 작은 원소를 리턴한다. (오름차순)
pq.get()
시간복잡도는 O(log N)이다.
5) 정렬 기준 변경
(우선순위, 값)의 튜플의 형태로 데이터를 추가 및 제거하면 된다.
ex. 내림차순정렬 하고 싶은 경우
pq.put((-element, element))
Max = pq.get()[1]
3. 문제 풀이
2020/12/04 - [프로그래밍/Python] - 프로그래머스 - 좌석 구매