백준 1927 최소 힙 (python) 🥈 실버2

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

 

 

카카오 공채 문제를 풀다가 최소 힙을 이용하는 문제가 나왔는데 기억이 하나도 안 나서 복습해볼꺼다. ~~

 

🦴힙 자료구조

- 힙은 특정 규칙을 갖는 트리이다.

- 최댓값과 최솟값 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다.

- A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소관계 성립

 

🦴최소 힙 : 부모 노드의 키값 < 자식 노드의 키값

             -> 최솟값이 루트에 

 

🦴최대 힙 :  부모 노드의 키값 > 자식 노드의 키값

              -> 최댓값이 루트에

키값의 대소관계는 부모-자식간에만 성립,

형제노드 사이에는 대소관계가 정해지지 않는다.

 

 

🦴파이썬 힙 자료구조

 

파이썬 heapq 모듈은 heapq (priority queue) 알고리즘을 제공한다.

모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리(binary tree) 구조

내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2) 보다 작거나 같은 최소 힙의 형태로 정렬된다.   

heapq는 내장 모듈로 별도의 설치 작업 없이 바로 사용할 수 있다.

 

힙 함수

heapq.heqppush(heqp, item) //item을 heap에 추가

heapq.heappop(heap) // heap에서 가장 작은 원소를 pop &리턴. (비어있으면 IndexError)

heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환. (O(N))

 

 

import heapq

heap = []
heapq.heappush(heap,123)
heapq.heappush(heap,1)
heapq.heappush(heap,2)
heapq.heappush(heap,3)
heapq.heappush(heap,4)

print(heap)

[1, 3, 2, 123, 4]

 

이미 생성해둔 리스트가 있다면 heapify 함수를 통해 즉각적으로 힙 자료형으로 변환할 수 있다.

 

import heapq

heap2 = [123,2,3,1]
heapq.heapify(heap2)
print(heap2)

[1, 2, 3, 123]

 

heappop

- 원소 삭제

- 가장 작은 원소를 제거 & 리턴

 

import heapq

heap2 = [123,2,3,1]
heapq.heapify(heap2)

result = heapq.heappop(heap2)
print(result) //1
print(heap2)

1
[2, 123, 3]

 

원소를 삭제하지 않고 가져오고싶다면? -> 인덱스[0]으로 최솟값을 가져오면 된다

import heapq

heap = [123,2,3,1]
heapq.heapify(heap)

result = heap[0]
print(result)
print(heap)

1
[1, 2, 3, 123]

 

파이썬에서 기본적으로 제공하는건 최소힙.

최대힙을 구현하려면?

 

import heapq

heap = [123, 2, 3, 1]
max_heap = []

for item in heap:
    heapq.heappush(max_heap, (-item, item))  #튜플형태로 push 할수도 있다!!

print(max_heap)  #[(-123, 123), (-2, 2), (-3, 3), (-1, 1)]
result = max_heap[0][1]  #(-123,123) 튜플의 [1]번째 원소 -> 123
print(result)  #123

max_item = heapq.heappop(max_heap)[1]
print(max_item)#123

------------------------------------------------------------------------------------------------------------------

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

 

시도1 (실패)

import heapq
n = int(input())
heap = []
result = []

for _ in range(n):
    x = int(input())
    if x == 0:  #입력값 x가 0이 들어왔을 때
        if len(heap) == 0:  #heap이 비어있으면 결과에 0추가
            result.append(0)
        else: #힙에서 최솟값을 추출한 뒤 결과리스트에 추가
            result.append(heapq.heappop(heap))
    else: #0이 아닌 x가 입력되면
        heapq.heappush(heap, x) #힙에 x를 추가

for item in result:
    print(item)

결과는 잘 나오는데 시간초과가 나서

구글링해보니

반복문으로 여러줄 입력받는 상황에서는 반드시 sys.stdin.readline()을 사용해야 시간초과가 발생하지 않는다고 한다.

엄청난 깨달음..!

import heapq
import sys

read = sys.stdin.readline

n = int(input())
heap = []
result = []

for _ in range(n):
    x = int(read())
    if x == 0:  #입력값 x가 0이 들어왔을 때
        if len(heap) == 0:  #heap이 비어있으면 결과에 0추가
            result.append(0)
        else: #힙에서 최솟값을 추출한 뒤 결과리스트에 추가
            result.append(heapq.heappop(heap))
    else: #0이 아닌 x가 입력되면
        heapq.heappush(heap, x) #힙에 x를 추가

for item in result:
    print(item)

오왕

 

실버4로 승급도 했다 ><