<div id="readability-page-1" class="page"><div><p data-ke-size="size16"><b>Question.</b></p>

<p data-ke-size="size16">최소 힙을 구현하는 문제이다.</p>

<figure data-origin-width="1175" data-origin-height="844" data-ke-mobilestyle="widthOrigin"><span data-url="https://blog.kakaocdn.net/dn/bNBgeG/btq7tb1UtH9/Oro2iXwQc7LK1YDC3Znho1/img.png" data-lightbox="lightbox" data-alt=""><img src="https://blog.kakaocdn.net/dn/bNBgeG/btq7tb1UtH9/Oro2iXwQc7LK1YDC3Znho1/img.png" data-origin-width="1175" data-origin-height="844" data-ke-mobilestyle="widthOrigin"></span></figure>


<hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style1">
<p data-ke-size="size16"><b>Answer.</b></p>

<p data-ke-size="size16">처음 파이썬으로 코딩테스트를 볼 때, heapq 모듈을 사용하는 방법을 몰라 헤맸던 기억이 난다.</p>

<p data-ke-size="size16">코딩테스트에 heapq는 자주 나오니까 아래 내용을 익혀두자.</p>

<p data-ke-size="size16"><a href="https://www.daleseo.com/python-heapq/" target="_blank" rel="noopener">https://www.daleseo.com/python-heapq/</a></p>
<figure id="og_1623855922204" contenteditable="false" data-ke-type="opengraph" data-ke-align="alignCenter" data-og-type="website" data-og-title="[파이썬] heapq 모듈 사용법" data-og-description="Engineering Blog by Dale Seo" data-og-host="www.daleseo.com" data-og-source-url="https://www.daleseo.com/python-heapq/" data-og-url="https://www.daleseo.com/python-heapq/" data-og-image=""><a href="https://www.daleseo.com/python-heapq/" target="_blank" rel="noopener" data-source-url="https://www.daleseo.com/python-heapq/">

<div>
<p data-ke-size="size16">[파이썬] heapq 모듈 사용법</p>
<p data-ke-size="size16">Engineering Blog by Dale Seo</p>
<p data-ke-size="size16">www.daleseo.com</p>
</div>
</a></figure>

<p data-ke-size="size16">(내 풀이)</p>
<pre id="code_1623855790108" data-ke-language="python" data-ke-type="codeblock"><code>import heapq
import sys

input = sys.stdin.readline  ## 시간초과 방지

N = int(input())
heap = []
for _ in range(N):
    x = int(input())
    if x == 0:
        if not heap:
            print(0)
        else:
            print(heapq.heappop(heap))
    else:
        heapq.heappush(heap, x)</code></pre>

<table data-ke-align="alignLeft">
<tbody>
<tr>
<td colspan="2">sol 1)&nbsp;</td>
</tr>
<tr>
<td>Time Complexity</td>
<td>O(NlogN)</td>
</tr>
<tr>
<td>Space Complexity</td>
<td>O(N)</td>
</tr>
</tbody>
</table>

            
</div></div>

sohyunwriter

Question.
 
최소 힙을 구현하는 문제이다.
 
 
 
Answer.
 
처음 파이썬으로 코딩테스트를 볼 때, heapq 모듈을 사용하는 방법을 몰라 헤맸던 기억이 난다.
 
코딩테스트에 heapq는 자주 나오니까 아래 내용을 익혀두자.
 
https://www.daleseo.com/python-heapq/
 
(내 풀이)
import heapq
import sys
input = sys.stdin.readline  ## 시간초과 방지
N = int(input())
heap = []
for _ in range(N):
    x = int(input())
    if x == 0:
        if not heap:
            print(0)
        else:
            print(heapq.heappop(heap))
    else:
        heapq.heappush(heap, x)
 
sol 1) 
Time Complexity
O(NlogN)
Space Complexity
O(N)

백준 1927. 최소 힙 (+파이썬 풀이)

댓글