[백준] 실버2 최소 힙, 최대 힙

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

1927번: 최소 힙

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

11279번: 최대 힙

solve.ac에 있는 Class 3의 문제를 푸는데 마침 두 문제를 동시 풀 수 있는 개꿀따리가 나타났다.

 

2학년 자료구조 시간에 heap 이라는 자료구조를 배웠었다. 이 구조를 이용하여 문제를 푸는 것이다.

파이썬의 엄청난 기능을 활용할 수 있는 때는 지금과 같은 상황이다.

 

원래는 Tree 구조로 해서 직접 heap 구조를 만들어야 한다. 

 

하지만, 파이썬은....

from heapq import heappush, heappop

이걸로 모든게 끝이다. 

 

하나의 리스트를 만든 뒤, heappush 및 heappop 연산을 해주면 알아서 heap 구조를 유지시키면서 원활한 연산을 해줌과 동시에 시간복잡도 마저도 효율적이게 해준다.

heappush같은 경우 O(log n), heappop은 O(1)로 두게끔 해준다.

 

but, 최소 힙 문제는 아무래도 입력하고자 하는 값들이 많기 때문에 import sys를 통해 sys.stdin.readline() 입력을 받게끔 해야했다.

그래야 성공할 수 있었다.

최소힙

다음으로는, 최대힙 문제이다.

이전의 최소힙과 차이점은 원래 heapify()(?)라는 것을 통해 최소 힙을 나열해보면 오름차순으로 구조가 이루어짐을 알 수 있다. 

하지만, 최대힙은 내림차순 이라는 것이다.

 

그러면 기존의 heap 자료구조를 어떻게 이용하면 될까?

 

heappush의 연산자는 항상 첫번째 입력값에 대해 들어가고자 하는 heap의 위치에 들어가게되는데 이를 이용할 수 있다.

heappush의 입력을 n을 받아야할때, tuple 형식으로 -n, n을 받는 것이다. 

그러면 heappop을 할때 0번째가 아닌 1번째 인덱스를 출력하게 하면 내림차순으로 출력되는 것을 확인할 수 있다.

 

tuple 형식도 입력으로 사용할 수 있다는 것을 이용하여 최대힙을 손쉽게 구현할 수 있었다.

최대힙

1일 1백준 22일째...