[백준 알고리즘] 11279번: 최대 힙(우선순위 큐) - Python

 

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

11279번: 최대 힙

 

[문제]

 

[제출한 코드 및 풀이]

실패코드(시간초과 1)

- stack이라는 리스트를 만들어두고 x를 입력 받으면 항상 sort를 해준다.

- x가 0일 때, stack의 길이가 0일 경우 0을 출력하고 길이가 0이 아닐 경우 stack의 가장 큰 값을 출력 후 stack에서 제거한다.

- x가 0이 아닐 때, stack에 x를 추가한다.

 

실패코드(시간초과 2)

- 일단 여기서 원인이 코드 자체의 문제가 아니라 입력 때문이라는 것을 알았다.

 

성공코드

- 입력 받는 부분을 변경 했더니 시간초과 에러가 사라졌다!

 

- heapq는 최소 힙으로 구현되어 있기 때문에 최대 힙 구현 문제에서는 살짝 바꿔줘야했다.

- 11번째 라인은 heapq 모듈의 heappush를 사용해서 stack에 튜플 형태의 (-x, x) 를 넣어줬다. 힙에 원소를 추가할 때 (-x, x) 형태로 넣어주면 첫 번째 원소를 우선순위로 하여 힙을 구성하게 된다. 다만 여기서 음수의 부호이기 때문에 최소 힙 구현을 최대 힙 구현으로 변경하여 활용할 수 있다.

- 14번째 라인에서 heapq.heappop을 사용하였는데 heappop을 사용하면 힙에서 가장 작은 항목을 pop하고 반환한다. 실제로는 음수 자리가 아니라 인덱스 1번 자리에 있으므로 [1]로 접근해서 출력되게 했다.

*힙이 비어 있을 경우 IndexError가 발생한다. 

 

 

 

[출력결과 및 채점 결과]

- 첫번째 시도 후 시간 초과 실패!

 

- 드디어 성공...

 

 

다른 사람의 코드

- 최대 힙 자체를 직접 구현한 코드

https://hooongs.tistory.com/130

[백준11279번] 최대 힙 / Python3

 

 

References

https://docs.python.org/ko/3/library/heapq.html

heapq — 힙 큐 알고리즘 — Python 3.10.2 문서