[백준/python] 11286번 절댓값 힙

1. 문제 

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

11286번: 절댓값 힙

 

2. 힙(Heap)

힙이란 특정한 규칙을 가지며 완전이진트리을 기본으로 한다. 최댓값, 최솟값 연산을 빠르게 하기 위해 사용된다 ! 

이 문제에서도 절댓값의 최솟값부터 출력하라고 했다 ! 

파이썬의 heapq 모듈로 힙 자료구조 사용하기

모듈에 관한 코드는 이 링크를 통해 참조하고 절댓값 함수만 씌워주었다 !! 

 

3. 풀이

heap 모듈을 통해 push해주는데 이때 절댓값의 최소부터 출력하니 abs내장함수를 사용한다. 

실제값은 튜플의 [1]번째 인덱싱에 들어있으니 이를 pop해주면 된다.

 

어찌저찌 모듈을 써서 구현을 하긴 했지만 이해안가는 부분도 꽤 있었다. 이게 왜 되지? 싶은

조금 더 이해를 쉽게하기 위해 반복문에 print를 넣어보았다. 

 

from heapq import heappush,heappop
import sys

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

for i in range(n):
    num = int(sys.stdin.readline())
    print("-----값 입력받기-----")
    print(i+1,"번째 입력받은 수 : ",num)
    if num ==0:
        try:
            print("pop하기 전 배열은 : ", heap)
            print(heappop(heap)[1])
            print("pop한 뒤 배열은 :", heap)
        except:
            print("except발생 ")
            print(0)


    else:
        heappush(heap,(abs(-num),num))
        print("heap푸쉬함 :" ,heap)

프로그램결과는 다음 접은글과 같다 ! 

-----값 입력받기-----
1 번째 입력받은 수 :  1
heap푸쉬함 : [(1, 1)]
-----값 입력받기-----
2 번째 입력받은 수 :  -1
heap푸쉬함 : [(1, -1), (1, 1)]
-----값 입력받기-----
3 번째 입력받은 수 :  0
pop하기 전 배열은 :  [(1, -1), (1, 1)]
-1
pop한 뒤 배열은 : [(1, 1)]
-----값 입력받기-----
4 번째 입력받은 수 :  0
pop하기 전 배열은 :  [(1, 1)]
1
pop한 뒤 배열은 : []
-----값 입력받기-----
5 번째 입력받은 수 :  0
pop하기 전 배열은 :  []
except발생 
0
-----값 입력받기-----
6 번째 입력받은 수 :  1
heap푸쉬함 : [(1, 1)]
-----값 입력받기-----
7 번째 입력받은 수 :  1
heap푸쉬함 : [(1, 1), (1, 1)]
-----값 입력받기-----
8 번째 입력받은 수 :  -1
heap푸쉬함 : [(1, -1), (1, 1), (1, 1)]
-----값 입력받기-----
9 번째 입력받은 수 :  -1
heap푸쉬함 : [(1, -1), (1, -1), (1, 1), (1, 1)]
-----값 입력받기-----
10 번째 입력받은 수 :  2
heap푸쉬함 : [(1, -1), (1, -1), (1, 1), (1, 1), (2, 2)]
-----값 입력받기-----
11 번째 입력받은 수 :  -2
heap푸쉬함 : [(1, -1), (1, -1), (1, 1), (1, 1), (2, 2), (2, -2)]
-----값 입력받기-----
12 번째 입력받은 수 :  0
pop하기 전 배열은 :  [(1, -1), (1, -1), (1, 1), (1, 1), (2, 2), (2, -2)]
-1
pop한 뒤 배열은 : [(1, -1), (1, 1), (1, 1), (2, -2), (2, 2)]
-----값 입력받기-----
13 번째 입력받은 수 :  0
pop하기 전 배열은 :  [(1, -1), (1, 1), (1, 1), (2, -2), (2, 2)]
-1
pop한 뒤 배열은 : [(1, 1), (1, 1), (2, 2), (2, -2)]
-----값 입력받기-----
14 번째 입력받은 수 :  0
pop하기 전 배열은 :  [(1, 1), (1, 1), (2, 2), (2, -2)]
1
pop한 뒤 배열은 : [(1, 1), (2, -2), (2, 2)]
-----값 입력받기-----
15 번째 입력받은 수 :  0
pop하기 전 배열은 :  [(1, 1), (2, -2), (2, 2)]
1
pop한 뒤 배열은 : [(2, -2), (2, 2)]
-----값 입력받기-----
16 번째 입력받은 수 :  0
pop하기 전 배열은 :  [(2, -2), (2, 2)]
-2
pop한 뒤 배열은 : [(2, 2)]
-----값 입력받기-----
17 번째 입력받은 수 :  0
pop하기 전 배열은 :  [(2, 2)]
2
pop한 뒤 배열은 : []

-----값 입력받기-----
18 번째 입력받은 수 :  0
pop하기 전 배열은 :  []
except발생 
0

 

 

처음에는

num = [int(input()) for _ in range(n)]

num 배열을 통해 입력받은 값을 하나하나 탐색해보며 진행해보았다. 

값은 나오지만 시간초과 .. 그래서 sys함수를 통해 하나씩 입력받으며 바로 heap배열에 넣어보았다. 

 

대부분 input을 넣어서 시간초과가 뜨는 결과를 자주 보았는데.. sys로 먼저 풀어보려고 노력해야겠다 !! 

 

4. 코드

from heapq import heappush,heappop
import sys

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

for i in range(n):
    num = int(sys.stdin.readline())
    if num ==0:
        try:
            print(heappop(heap)[1])
        except:
            print(0)


    else:
        heappush(heap,(abs(-num),num))