혀니의 이거저거 뿌시기

백준 11279 최대 힙 본문

알고리즘 공부(C++)

백준 11279 최대 힙

혀니리리 2022. 8. 28. 15:01
728x90

11279번: 최대 힙 (acmicpc.net)

 

11279번: 최대 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가

www.acmicpc.net

import heapq
import sys
N = int(input())
heap = []
for i in range(N):
    x = int(sys.stdin.readline())
    if x == 0:
        if not heap:
            print(0)
        else:
            print(heapq.heappop(heap)[1])
    else:
        heapq.heappush(heap, (-x, x))

힙.이라는 것을 처음 접해보았읍니다.

힙은 부모를 가장 작은 값의 상태로 유지하는 자료구조라고 해요.

그런데 가장 큰값을 위로 가게 하려면 위와 같은 방법이 있다구 하네요..

그 방법은 각 리스트에 넣을때 넣는 값을 튜플로 만들어서 - 씌운 값을 0인덱스로 하고

출력할 때는 1인덱스를 출력하는 방법이라고 합니다.

다들 알아두셔요..

728x90

'알고리즘 공부(C++)' 카테고리의 다른 글

백준 2075 N번째 큰 수 -heap  (0) 2022.08.28
백준 1715 카드 정렬하기 - 힙  (0) 2022.08.28
백준 15650 N과 M(2) - 백트래킹문제  (0) 2022.08.28
백준 3986 좋은 단어  (0) 2022.08.27
백준 18258 큐2  (0) 2022.08.27
'알고리즘 공부(C++)' Related Articles more