코딩테스트 준비 - 프로그래머스: 더 맵게 풀이/heap에 대하여 (파이썬)

---

프로그래머스: 더 맵게 - 풀이

---

포스팅 요약

1. 문제 풀이

2. heapq 에 대하여 (간략하게)

---

문제풀러가기

https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

---

문제

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

---

풀이

1. sort()보다 heapq를 사용하여 min값(혹은 max값)을 구하는 것이 효율성이 더 좋다

---

코드 (실패: 시간 초과 )

def solution(scoville, K): 
    scoville.sort()
    now=0            
    cnt=0
    if scoville[0]>=K:
        return 0
    while scoville[0]<K:  
        now = scoville[0] + (scoville[1]*2)
        cnt+=1
        if len(scoville)>=3:
            scoville=[now]+scoville[2:]
        else:       
            if sum(scoville)<K:
                return -1
        scoville.sort()
                
    return cnt

 

코드 (성공)

import heapq
def solution(scoville, K): 
    heapq.heapify(scoville)           
    cnt=0
    while scoville[0]<K:
        if len(scoville)<=1 and scoville[0]<K:
            return -1
        heapq.heappush(scoville,heapq.heappop(scoville)+(heapq.heappop(scoville)*2))
        cnt+=1          
    return cnt

---

heapq에 대하여

*완전 이진 트리 자료구조의 일종

heapq.heapify(list): list를 heap으로 변환. (시간 복잡도:O(N))

heappush(list, item): list 안에 item 추가. (시간 복잡도:O(log N))

heappop(list): list에서 가장 작은 원소를 pop/ len(list)=0일 경우 IndexError. (시간 복잡도: O(log N))

import heapq
list = [5,2,9]
heapq.heapify(list)
print(list) #[2, 5, 9]
print(list[0]) # 2

heapq.heappush(list,1) 
print(list) #[1, 2, 9, 5]

print(heapq.heappop(list)) # 1
print(heapq.heappop(list)) # 2
print(heapq.heappop(list)) # 5
print(heapq.heappop(list)) # 9
#print(heapq.heappop(list)) #주석을 뺄 경우 IndexError 발생

최소 힙일 경우

최소 힙(min heap)

- 루트노드가 가장 작은 값은 가진다. 

- heapq.heappop(list)를 할 경우 가장 작은 값 제거. (루트부터 제거)

 

최대 힙(max heap)

- 루트노드가 가장 큰 값은 가진다.

- heapq.heappop(list)를 할 경우 가장 큰 값 제거.(루트부터 제거)

 

heap 에서 부모노드와 자식노드의 관계

왼쪽 자식 Index = (부모 Index)*2 

오른쪽 자식 Index = (부모 Index)*2 +1

*구현 하기 쉽게 하기위해 index 0은 사용하지 않는다.

---

배운점

1. heapq.heapify를 사용하여 list를 heap으로 변환할 경우 list[0]은 무조건 list 원소중 제일 작은 원소.

2. 탐색을 하기위해 사용하지는 않음. (탐색의 경우 BFS 혹은 DFS를 많이 사용)