[알고리즘/자료구조] 11286번 : 절댓값 힙 - python

링크 : https://www.acmicpc.net/problem/11286

11286번: 절댓값 힙

 

---

• 문제
• 소요시간: 21분 12초

---

• 설계하기(접근방법) 

1. n을 입력받는다, heapq를 두 개 선언한다

2. 알고리즘 해석

1) x = int(input()) 을 받는다

x > 0 이면 heap_plus에 (x)를

x < 0 이면 heap_minus에 (-x)를 heappush 한다

x = 0일 때는

   i) heap_plus, heap_minus 둘 다 원소가 있을 때

        절대값이 작은 쪽을 출력하고, 같다면 heap_minus에서 heappop()후 출력한다

 

  ii) heap_plus에만 원소가 있을 때 heappop()후 출력한다

 

 iii) heap_minus에만 원소가 있을 때 heap_minus에서 heappop()을 해주고 부호를 바꿔 출력한다

 

 iv) 둘다 비었을 때는 0을 출력한다

---

• 코드(출력)

import heapq
import sys

heap_plus = []
heap_minus = []

n = int(input())

for i in range(n):
    x = int(sys.stdin.readline())
    if x == 0:
        if heap_minus and heap_plus:
            if abs(heap_minus[0]) > abs(heap_plus[0]):
                print(heapq.heappop(heap_plus))
            elif abs(heap_minus[0]) < abs(heap_plus[0]):
                print(-heapq.heappop(heap_minus))
            elif abs(heap_minus[0]) == abs(heap_plus[0]):
                print(-heapq.heappop(heap_minus))
        elif heap_plus and not heap_minus:
            print(heapq.heappop(heap_plus))
        elif heap_minus and not heap_plus:
            print(-heapq.heappop(heap_minus))
        else:
            print(0)
    if x > 0:
        heapq.heappush(heap_plus, x)
    if x < 0:
        heapq.heappush(heap_minus, -x)

다른 분들의 더 좋은 코드이다

import sys
import heapq

n = int(input())
heap = []

for i in range(n):
    a = int(sys.stdin.readline().rstrip())
    if a != 0: # a가 0이 아니라면, a의 절댓값과 a 함께 push
        heapq.heappush(heap, (abs(a), a))
    else:
        if not heap: # 힙이 비어있다면
            print(0)
        else:
            print(heapq.heappop(q)[1]) # 힙의 원래값 출력

---

• 얻어갈 부분

1. 힙에 이중배열로 넣어도 0번째 index값이 같은 경우에는 1번재 index의 값도 고려하여 최소값을 가장 끝단에 넣는다.

2. 절댓값을 사용하고 싶은 경우 abs() 메서드를 사용하면 된다.