[백준][heap] 최대 힙, 절댓값 힙 python (200729)

 

최대힙과 절대값 힙은 앞에 포스팅에서 풀이를 했던 최소 힙에서 약간만 응용하면 아주 쉽게 풀린다 ! 

 

https://huidea.tistory.com/29?category=879544

[백준][heap] 최소힙 python (200726)

 

우선 최대힙 부터 살펴보자면, 

[ 최대힙 ] 

1. 문제 설명 

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

11279번: 최대 힙

 

 

 

2. 풀이 - 최대 힙을 만들자!

앞에서 풀었던 최소힙은 python 의 heapq 모듈을 활용해서 힙 자료구조 형태를 만들어 풀었다. 

이번에도 그렇게 풀면 되는데, 문제는  python 의 heapq 모듈은 최소 값이 pop 되는, 최소힙이라는 것... 

그렇담 이걸 어떻게 바꾸면 좋을지 고민을 했는데,

 

숫자를 힙에 입력할때 (-num, num) --> 이처럼 튜플로 입력하면 된다. 우선 코드를 통해보자면, 

 

import heapq
import sys

N = int(input())
heap_list = []

for idx in range(N):
    num = int(sys.stdin.readline())
    print(">>",'idx', idx,'num', num, len(heap_list))
    if num != 0:
        heapq.heappush(heap_list, (-num,num)) #num 앞에 음수를 붙인뒤 튜플로 묶기!
    else:
        try:
            print(heapq.heappop(heap_list)[1])
        except IndexError:
            print(0)

0) 숫자를 입력받고, 0이아니면 heappush / 0이면 heappop

1) push 할 때 -  num 에 입력되는 숫자가 크면 클수록 튜플의 첫번째 자리의 숫자는 작아지게 된다. (음수로 바꿔주니까)

그리고 튜플은 첫번째 요소를 기준으로 정렬이 된다. (만약 첫번째 요소 같으면, 두번째 요소로 넘어가는 방식)

 

2) 그리고 heappop 을 통해 출력할때는 고유의 num 만 출력되도록 [1] 인덱싱 

 

 

[ 절댓값 힙 ] 

1. 문제설명

11286번: 절댓값 힙

2. 풀이 - abs 만 씌우면 뚝딱

# 최대힙에서 응용
import heapq
import sys

N = int(input())
heap_list = []

for idx in range(N):
    num = int(sys.stdin.readline())
    if num != 0:
        heapq.heappush(heap_list, (abs(num),num))
    else:
        try:
            print(heapq.heappop(heap_list)[1])
        except IndexError:
            print(0)

 

위의 문제에 -num 대신 abs(num) 으로 하면 된다. 그럼 튜플은 절대값을 씌운 abs(num) 을 기준으로 정렬이 될꺼고, 

 

만약 abs(num) 절대값이 같은 상황이라면, 튜플의 두번째 요소 원래숫자 num 을 기준으로 정렬될테니 

문제에서 제시하는 요구사항을 쉽게 충족할 수 있다.!

 

 

 

3. 정리 및 더알아보기 

(-num,num) (abs(num),num) 분명 이 아이디어는 다른 알고리즘 문제에도 적용할 수 있을 듯!! 

 

이 비슷한 걸 어디서 적용해봤더라 곱씹어보니

각 튜플의 요소에서 오름 차순과 내림차순을 동시에 적용하려했던 문제에서 

 

 ffinal_list = sorted(final_list, key=lambda x: (-x[0], -x[1], x[2]))   이렇게 코드를 짠적이 있다. 

 final_list 의 요소가 3차원 튜플인데 첫번째요소는 내림차순, 두번째 요소는 내림차순, 세번째 요소는 오름차순 이렇게 만드는 코드다

 

해당 문제: 

https://huidea.tistory.com/5?category=879544

[프로그래머스][hash] 베스트앨범 python (200715)