파이썬) 최소힙, heapq

알고 넘어가야 할 이론:

자료구조 힙:

https://www.youtube.com/watch?v=Zl07LUsR6P0 

 

파이썬 힙과 관련된 코드:

heappush :

힙에 원소 추가하기 heappush(배열,추가할원소)

import heapq

my_heap = []

heapq.heappush(my_heap,5)
print(f'my_heap 5 추가 = {my_heap}')
heapq.heappush(my_heap,4)
print(f'my_heap 4 추가 = {my_heap}')
heapq.heappush(my_heap,3)
print(f'my_heap 3 추가 = {my_heap}')
heapq.heappush(my_heap,2)
print(f'my_heap 2 추가 = {my_heap}')
heapq.heappush(my_heap,1)
print(f'my_heap 1 추가 = {my_heap}')

결과값:

my_heap 5 추가 = [5]
my_heap 4 추가 = [4, 5]
my_heap 3 추가 = [3, 5, 4]
my_heap 2 추가 = [2, 3, 4, 5]
my_heap 1 추가 = [1, 2, 4, 5, 3]

heappop :

힙에 원소 삭제하기 heappop(배열)

파이썬은 최소힙을 지원하기 때문에 

heappop을 하게되면 배열의 가장 작은 값이 삭제되게 된다.

my_heap = [1,2,4,5,3]

print(f'현재 my_heap = {my_heap}')
print(f'my_heap 삭제될 원소값 = {my_heap[0]}')
heapq.heappop(my_heap)
print(f'현재 my_heap = {my_heap}')
print(f'my_heap 삭제될 원소값 = {my_heap[0]}')
heapq.heappop(my_heap)
print(f'현재 my_heap = {my_heap}')
print(f'my_heap 삭제될 원소값 = {my_heap[0]}')
heapq.heappop(my_heap)
print(f'현재 my_heap = {my_heap}')
print(f'my_heap 삭제될 원소값 = {my_heap[0]}')
heapq.heappop(my_heap)
print(f'현재 my_heap = {my_heap}')
print(f'my_heap 삭제될 원소값 = {my_heap[0]}')
heapq.heappop(my_heap)
print(f'my_heap = {my_heap}')

 

결과값:

현재 my_heap = [1, 2, 4, 5, 3]
my_heap 삭제될 원소값 = 1
현재 my_heap = [2, 3, 4, 5]
my_heap 삭제될 원소값 = 2
현재 my_heap = [3, 5, 4]
my_heap 삭제될 원소값 = 3
현재 my_heap = [4, 5]
my_heap 삭제될 원소값 = 4
현재 my_heap = [5]
my_heap 삭제될 원소값 = 5
my_heap = []

 

heappushpop:

힙에 원소 추가와 동시에 최소힙 삭제하기 heappushpop(배열,추가할 원소)

heappushpop 은 새로운 원소를 추가함과 동시에 배열[0]에 있는값을 삭제한다.

import heapq

my_heap = [5,4,3,2,1]

print(f'현재 my_heap = {my_heap}')

heapq.heappushpop(my_heap,6)
print(f'현재 my_heap = {my_heap}')
heapq.heappushpop(my_heap,7)
print(f'현재 my_heap = {my_heap}')
heapq.heappushpop(my_heap,8)
print(f'현재 my_heap = {my_heap}')
heapq.heappushpop(my_heap,9)
print(f'현재 my_heap = {my_heap}')
heapq.heappushpop(my_heap,10)

print(f'현재 my_heap = {my_heap}')

결과값 :

현재 my_heap = [5, 4, 3, 2, 1]
현재 my_heap = [3, 4, 6, 2, 1]
현재 my_heap = [4, 1, 6, 2, 7]
현재 my_heap = [1, 2, 6, 8, 7]
현재 my_heap = [2, 7, 6, 8, 9]
현재 my_heap = [6, 7, 10, 8, 9]

heapify:

기존 리스트의 값을 힙정렬 해줘서 최소힙이 인덱스[0]에 오도록 해준다.

import heapq

my_heap = [5,4,3,2,1]

print(f'현재 my_heap = {my_heap}')
heapq.heapify(my_heap)
print(f'힙정렬하고 난 후의 my_heap = {my_heap}')

 

결과값:

현재 my_heap = [5, 4, 3, 2, 1]
힙정렬하고 난 후의 my_heap = [1, 2, 3, 5, 4]

 

https://www.daleseo.com/python-heapq/

 

sys.stdin.readline:

import sys
a = int(sys.stdin.readline())

sys.stdin.readline()은 한줄 단위로 입력받기 때문에, 개행문자가 같이 입력 받아진다.

만약 3을 입력했다면, 3\n 이 저장된다. 따라서 필요에따라 .split()을 사용해서 개행문자를 제거해야 한다.
또한, 변수 타입이 문자열 형태(str)로 저장되기 때문에, 정수로 사용하기 위해서 형변환을 거쳐야 한다.

 

https://velog.io/@yeseolee/Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%9E%85%EB%A0%A5-%EC%A0%95%EB%A6%ACsys.stdin.readline

---

오늘 공부한 내용

문제: 

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

 

문제

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력 1 

9
0
12345678
1
2
0
0
0
0
32

예제 출력 1 

0
1
2
12345678
0

내가 생각한 문제풀이 : 

import heapq

num = int(input())
a = []

for i in range(num):
    x = int(input())
    if x == 0 and len(a) == 0:
        print(0)
    elif x == 0:
        print(a[0])
        heapq.heappop(a)
    elif x > 0 :
        heapq.heappush(a, x)

 

정답코드:

import heapq
import sys

num = int(sys.stdin.readline())
a = []

for i in range(num):
    x = int(sys.stdin.readline())
    if x == 0 and len(a) == 0:
        print(0)
    elif x == 0:
        print(a[0])
        heapq.heappop(a)
    elif x > 0 :
        heapq.heappush(a, x)

 

코드분석 :

 

힌트 1 . 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산

힌트 2 .  x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거

힌트3. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력

----------------------------------------------------------------------------------------------------------------------------

처음 값 을 입력할때는 무조건 배열이 비어있게 된다.

배열이 비어있다는 것은 배열의 길이가 0이라는 소리니까.

if x == 0 and len(a) == 0:

조건을 넣어준다.

그 후, 자연수일때는 원소값을 추가하고 

0일때는 가장 작은값을 추가하고 그 값(가장 작은값)을 빼라고 했으니까 elif 를 활용해서 

조건을 넣어준다. 그리고 배열을 계속 정렬해야하니 heappop을 활용하여 값을 제거해준다.

elif x == 0:
    print(a[0])
    heapq.heappop(a)

그 다음 자연수일때는 값을 추가하라고 하였으니 heappush를 이용해서 값을 추가해준다.

elif x > 0 :
    heapq.heappush(a, x)

 

---

더 공부할 내용

input()을 사용하여 입력값을 받았을때 시간초과가 났다.

int(sys.stdin.readline()) 를 사용하면 시간초과가 나지 않았다.

 

input() 과 sys.stdin.readline()의 차이점은 뭘까?

결론적으로 input() 내장 함수는 sys.stdin.readline()과 비교해서 prompt message를 출력하고, 개행 문자를 삭제한 값을 리턴하기 때문에 느리다.

따라서 맨 첫줄의 테스트케이스로 값을 받을때는 괜찮지만 반복문으로 입력값을 계속 받아야 할 경우에는  sys.stdin.readline()을 활용해서 입력을 받는 것이 좋다.

 https://buyandpray.tistory.com/7

---

느낀점

프로그래머스만 풀다가 백준을 처음 풀어서 그런지

입력값을 받는 방법에대해 어려움을 느꼈다.