Jinho Tech

기본적인 우선순위 큐 문제이다. 이 문제도 골드 4 난이도 치고는 쉽다.

우선순위 큐에 남은 수가 2개 이하가 되기 전까지 제일 작은 두 값을 pop 해서 더하고,

그 합을 우선순위 큐에 추가하고 res에 더해주면 된다. 마지막에 res를 출력해주면 끝

import heapq
import sys
input = sys.stdin.readline

N = int(input())
q = []
for _ in range(N):
    n = int(input())
    heapq.heappush(q, n)
if N == 1:
    print(0)
else:
    res = 0
    while len(q) > 1:
        t = heapq.heappop(q)+heapq.heappop(q)
        res += t
        heapq.heappush(q, t)
    print(res)

골드 5 난이도 치고는 매우 쉬운 우선순위 큐 문제이다.

최대 힙 우선순위 큐로 구현해서 N번째 pop결과를 출력해주는 식으로 풀어도 답은 맞지만 메모리 초과가 뜬다.

heapq의 nlargest를 사용해서 해결했다 -> q값 중 제일 큰 N개의 값을 추출

import heapq

N = int(input())
q = []
for _ in range(N):
    for n in map(int, input().split()):
        heapq.heappush(q, n)
    q = heapq.nlargest(N, q)
heapq.heapify(q)
print(heapq.heappop(q))

기본적인 우선순위 큐 문제이다.

import heapq

n, m = map(int, input().split())
q = list(map(int, input().split()))
heapq.heapify(q)
for _ in range(m):
    a = heapq.heappop(q)
    b = heapq.heappop(q)
    heapq.heappush(q, a+b)
    heapq.heappush(q, a+b)
print(sum(q))

기본적인 우선순위 큐 문제이다. 파이썬에서 우선순위 큐는 heapq 라이브러리 또는 queue 라이브러리의

PriorityQueue를 사용하면 쉽게 구현할 수 있다. 나는 그냥 heapq 라이브러리를 사용해서 풀었다.

import heapq

n = int(input())
q = []
for _ in range(n):
    s = input()
    if s == '0':
        print(-heapq.heappop(q) if q else -1)
    else:
        li = list(map(int, s.split()))
        for n in li[1:]:
            heapq.heappush(q, -n)

기본적인 우선순위 큐 문제이다. 최대 힙으로 구현해주면 된다.

import heapq

N = int(input())
D = int(input())
q = []
for _ in range(N-1):
    n = int(input())
    heapq.heappush(q, -n)
res = 0
while q:
    n = -heapq.heappop(q)
    if D > n:
        break
    D += 1
    res += 1
    heapq.heappush(q, -(n-1))
print(res)

우선순위 큐를 사용해서 빠르게 중앙값을 찾아야 되는 문제이다.

우선순위 큐를 2개(최대 힙, 최소 힙) 사용한다는 점이 핵심이다. 왼쪽 우선순위 큐는 최대 힙으로 최댓값이 맨 처음에

오도록 구현하고, 오른쪽 우선순위 큐는 최소 힙으로 최솟값이 맨 처음에 오도록 구현한다.

왼쪽과 오른쪽 우선순위 큐의 크기가 똑같다면 왼쪽 우선순위 큐에 값을 저장하고, 왼쪽 우선순위 큐의 첫 번째 값이

오른쪽 우선순위 큐의 첫 번째 값보다 큰 경우가 생기면 왼쪽 값을 오른쪽 값으로 바꿔주면 된다.

마지막에는 왼쪽 우선순위 큐의 맨 처음 값(최대 힙의 최댓값)을 출력해주면 된다.

import heapq
import sys
input = sys.stdin.readline

N = int(input()) 
leftq, rightq = [], []
for _ in range(N):
    n = int(input())
    if len(leftq) == len(rightq):
        heapq.heappush(leftq, (-n, n))
    else:
        heapq.heappush(rightq, (n, n))
    if rightq and leftq[0][1] > rightq[0][1]:
        left, right = heapq.heappop(leftq)[1], heapq.heappop(rightq)[1]
        heapq.heappush(leftq, (-right, right))
        heapq.heappush(rightq, (left, left))
    print(leftq[0][1])

기본적인 우선순위 큐 문제이다.

import heapq
import sys
input = sys.stdin.readline

N = int(input()) 
q = []
for _ in range(N):
    n = int(input())
    if n != 0:
        heapq.heappush(q, (abs(n), n))
    else:
        print(heapq.heappop(q)[1] if q else 0)

우선순위 큐(Priority Queue)는 큐(Queue)나 스택(Stack)과 비슷한 축약 자료형이다.

일반적인 큐는 FIFO(First in-First Out) 구조이지만 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 

우선순위가 높은 데이터가 먼저 나오는 구조이다.

파이썬에서는 heapq 또는 PriorityQueue 라이브러리를 사용해서 우선순위 큐를 구현할 수 있다.

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []
for n in nums:
    heapq.heappush(heap, n)
while heap:
    print(heapq.heappop(heap))

heapq.heappush를 사용해서 우선순위 큐에 요소를 삽입하고, heapq.heappop을 사용해서 pop 할 수 있다.

heapq는 기본적으로 최소 힙이라서 값이 작은 (1, 3)부터 (3, 1), (10, 2)가 순서대로 pop 되는 것을 확인할 수 있다.

큰 것부터 pop 하고 싶다면 아래 코드와 같이 구현해주면 된다.

import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []
for n in nums:
    heapq.heappush(heap, (-n, n))
while heap:
    print(heapq.heappop(heap)[1], end=' ')
print()

아래 코드는 PriorityQueue를 사용해서 구현한 우선순위 큐이다.

from queue import PriorityQueue

q = PriorityQueue(maxsize=4)
q.put(3)
q.put(7)
q.put(2)
q.put(9)
print(q.get(), end= ' ')
print(q.get(), end= ' ')
print(q.get(), end= ' ')
print(q.get(), end= ' ')

우선순위 큐는 다익스트라 알고리즘이나, K번 째 최댓값을 찾을 때 등등에 사용할 수 있다.

아래는 대표적인 우선순위 큐 문제 풀이이다.

백준 11279번 최대 힙)

import heapq
import sys
input = sys.stdin.readline

N = int(input()) 
q = []
for _ in range(N):
    n = int(input())
    if n != 0:
        heapq.heappush(q, -n)
    else:
        print(-heapq.heappop(q) if q else 0)

백준 1927번 최소 힙)

import heapq
import sys
input = sys.stdin.readline

N = int(input()) 
q = []
for _ in range(N):
    n = int(input())
    if n != 0:
        heapq.heappush(q, n)
    else:
        print(heapq.heappop(q) if q else 0)

백준 알고리즘 문제 풀이)

jinho-study.tistory.com/1006

jinho-study.tistory.com/1007

jinho-study.tistory.com/1009

jinho-study.tistory.com/1010

jinho-study.tistory.com/1024

jinho-study.tistory.com/1026

jinho-study.tistory.com/1027

jinho-study.tistory.com/1067

jinho-study.tistory.com/1068

기본적인 우선순위 큐 문제이다.

import heapq
import sys
input = sys.stdin.readline

N = int(input()) 
q = []
for _ in range(N):
    n = int(input())
    if n != 0:
        heapq.heappush(q, n)
    else:
        print(heapq.heappop(q) if q else 0)

기본적인 우선순위 큐 문제이다.

import heapq
import sys
input = sys.stdin.readline

N = int(input()) 
q = []
for _ in range(N):
    n = int(input())
    if n != 0:
        heapq.heappush(q, -n)
    else:
        print(-heapq.heappop(q) if q else 0)