[백준] 11279번 최대 힙 - PYTHON

Flash·2022년 3월 16일
0

프로그래밍 문제

목록 보기
32/33

백준 11279번

최대 힙, 우선순위 큐

PYTHON

11279번 최대 힙


문제 이해

문제 자체는 간단하다.

최대 힙을 구현해서 0이 입력되면 pop연산을 자연수가 입력되면 insert연산을 수행한다.

배열이 비어있는 경우에 pop연산을 요구하면 0을 출력한다.


풀이 1

풀이 1은 직접 최대 힙 자료구조를 구현하는 것이다.

MaxHeap이라는 클래스를 구현해도 되지만 그냥 간단하게 함수만 선언하고 사용했다.

heapinsert와 heapremove는 함수 이름에서 알 수 있겠지만 삽입과 삭제 함수이다.

자료구조를 최대 힙으로 유지해주는 핵심은 heapify 함수이다.

Heapify 함수는 pop연산 이후에 호출하는데 재귀 함수의 형태로 되어 있다.

힙은 삭제 연산을 할 때, 최대 값 인덱스 1에 있는 값을 맨 뒤로 옮겨서 삭제한다. 그러면 인덱스 1에는 현재 옳지 않은 값이 들어있기 때문에 이 값의 위치를 찾아주어야 한다.

이 과정은 트리 구조로 생각했을 때, 왼쪽 자식, 오른쪽 자식과 비교해서 최대 값과 계속해서 교환해나가는 과정이다. 만약 양쪽 자식 값이 비교하는 값보다 작다면 그 위치가 올바른 위치이므로 재귀를 탈출한다.

Maxheap에서 인덱스 0에 0을 삽입해놓은 이유는 최대 힙의 인덱스를 1부터 시작하기 위함이다.


풀이 2

파이썬에는 heapq라고 하는 모듈이 존재한다. 이 모듈은 최소 힙을 구현해놓았다.

따라서 힙에 삽입할 때 (-cmd, cmd)의 형태로 삽입하는 것을 확인할 수 있다.
메모리 사용량이 풀이1보다 큰 이유인 것 같다.

중요한 것은 풀이1과 풀이2 모두 시간 제한을 통과해야 하기 때문에 sys 모듈을 사용해야 한다.

profile
Whiplash We Flash

0개의 댓글