[우선순위 큐- heapq] 백준 1655

우선순위 큐를 사용하는 문제입니다. 

파이썬에는 바로 사용가능한 heapq 모듈이 있어서 다음 코드를 사용해서 쉽게  문제를 풀었습니다. 

import heapq

 

1. 힙 생성하기

heapq모듈은 파이썬의 리스트를 힙처럼 다룰 수 있도록 합니다. 

따라서 그냥 빈 리스트를 생성하고, 함수를 호출할때마다 이 인자를 사용하면 됩니다. 

heap= []

 

2. 힙에 원소 추가하기

heappush() 함수를 사용해서 힙 리스트에 원소를 추가할 수 있습니다. 

함수의 첫번째 인자는 원소를 추가할 리스트이고, 두번째 인자는 추가할 원소입니다. 

heapq.heappush(heap, 1)

(heap 리스트에 원소 1을 추가하는 코드)

 

3. 힙에서 원소 삭제하기

heappop() 함수를 사용해서 힙 리스트의 원소를 삭제할 수 있습니다. 

heapq.heappop(heap)

 

백준 문제 1655번 풀이

 

 

우선순위 큐를 사용하는 문제입니다. 

처음에는 heap을 이용해서 중간값 인덱스를 구하면 되지 않을까 생각했는데 시간제한이 0.1초이기때문에 

시간 초과로 오류가 나게 됩니다. 

찾아본 풀이는 두개의 힙을 사용했다.

리스트 2개를 생성하고, 왼쪽과 오른쪽의 리스트 길이를 맞춰서 수를 넣으면 왼쪽 리스트의 가장 큰 값이 중간값이 된다. 

 

이때 다음과 같은 알고리즘을 사용한다. 

1. 두 리스트의 길이가 같으면 왼쪽 리스트에, 같지 않으면 오른쪽 리스트에 수를 추가한다. 

2. 왼쪽 리스트의 수에 -1을 곱해서 넣어서 정렬했을때 가장 큰 값이 가장 아래로 오도록 한다. 

3. 이때 왼쪽 리스트의 최소값이 오른쪽 리스트의 최소값보다 클 경우 두 값의 위치를 바꾸도록 한다. 

 

다음과 같은 알고리즘을 통해 새로운 값이 입력될때마다 그 에 맞는 중간값을 구할 수 있다. 

 

풀이 코드:

import sys
import heapq
input = sys.stdin.readline

max_h = []
min_h = []

n = int(input())

for i in range(n):
    num = int(input())
    if len(max_h) == len(min_h):
        heapq.heappush(max_h, -num)
    else:
        heapq.heappush(min_h, num)
    if len(max_h)>= 1 and len(min_h)>= 1 and max_h[0]* -1 > min_h[0]:
        max_value = heapq.heappop(max_h) * -1
        min_value = heapq.heappop(min_h)

        heapq.heappush(max_h, min_value * -1)
        heapq.heappush(min_h, max_value)

    print(max_h[0] * -1)