[그리디 알고리즘] 자료구조 우선순위 큐 2가지/BOJ 1715,1744

hyihyi·2022년 11월 16일
0

파이썬에서 제공하는 2가지 우선순위 큐 자료구조

📢우선순위 큐에 넣은 데이터들은 자동 정렬이 됨!

우선순위 큐를 사용하기 전 준비

📋from queue import PriorityQueue

1. PriorityQueue

<import>
from queue import PriorityQueue

<생성 방법>
myque = PriorityQueue() # myque를 우선순위 큐로 생성

<기본 함수>
put(data) 					# 원소 추가
get()						# 큐에서 데이터 꺼내기
qsize()						# 큐 사이즈 가져오기
empty()						# 큐가 비어있는지 확인

2. heapq

<import>
import heapq

<생성 방법>
mylist = []					# 리스트 생성
heapq.heappush(mylist, 1)	# 리스트에 데이터를 넣을 때 heapq를 이용하여 저장

<기본 함수>
heappush(mylist, data)		# data를 list(heap 자료구조) 형태로 저장
heappop(mylist)				# list(heap 자료구조)에서 데이터 꺼내기
heapify(mylist)				# 일반적인 list를 heap 자료구조로 변환

두 모듈의 차이점

PriorityQueue는 객체 자체를 우선순위 큐 형태로 만들어서 사용하는 반면 heapq는 기본적인 list 객체를 대상으로 원소 삽입, 삭제(꺼내기) 등의 제공 함수를 통해 우선순위 큐를 구현한다.


우선순위 큐를 이용한 문제 / BOJ 1715

from queue import PriorityQueue
N = int(input())        # 카드 묶음 개수
pq = PriorityQueue()    # 우선순위 큐

for _ in range(N):
    data = int(input())
    pq.put(data)        # 우선순위 큐에 데이터 저장
    
# 이렇게 우선순위 큐에 넣은 데이터들은 자동 정렬이 됨

data1 = 0
data2 = 0
sum = 0

while pq.qsize() > 1:   # 우선순위 큐에 데이터가 하나만 남을 때까지
    data1 = pq.get()    # 카드 2개 묶음을 큐에서 뽑음
    data2 = pq.get()
    temp = data1 + data2 
    sum += temp         # 카드 2개를 더하는데 필요한 비교횟수를 결과값에 더함
    pq.put(temp)        # 카드 2개의 합을 우선순위 큐에 다시 넣음

print(sum)              # 결과값 출력

📢우선순위 큐에 넣은 데이터들은 자동 정렬이 됨!


우선순위 큐를 이용한 문제 / BOJ 1744

from queue import PriorityQueue

N = int(input())
plusPq = PriorityQueue()
minusPq = PriorityQueue()
zero = 0
one = 0

for i in range(N):			# 데이터 분리 저장
    n = int(input())
    if n > 1:
        plusPq.put(n*-1)	# 양수 내림차순 정렬을 위해 -1을 곱하여 저장
    elif n == 0:
       zero += 1
    elif n == 1:
        one += 1
    else:
        minusPq.put(n)

sum = 0
while plusPq.qsize() > 1:		# 2개 이상 남았을 때
    data1 = plusPq.get() * -1
    data2 = plusPq.get() * -1
    sum += data1 * data2

if plusPq.qsize() > 0:			# 1개가 남았을 때(홀수)
    sum += plusPq.get() * -1

while minusPq.qsize() > 1:
    data1 = minusPq.get() * -1
    data2 = minusPq.get() * -1
    sum += data1 * data2

if minusPq.qsize() > 0:			# 1개가 남았을 때(홀수)
    if zero == 0:				# 0개수가 0개면 남은 수를 그냥 더함
    	sum += minusPq.get()
    # (만약 음수가 1개 남았고 0도 있으면 곱해서 음수를 상쇄시켜버림)
       
        

sum += one
print(sum)
profile
자유롭게 쓴 나의 자유로운 Development voyage⛵

0개의 댓글