[프로그래머스][힙(Heap)] 더 맵게

문제

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

프로그래머스

 

풀이

풀긴 풀었는데

heapq를 import 하지 않고선 방법이 없는건가..?

 

일단 아래는 heap 복습 겸 직접 구현해서 푼 풀이..

근데 heap 구현이 잘못됐는지 계속 틀린다.

def solution(scoville, K):
#     출력: 섞어야 하는 최소 횟수
    
#     2 <= len(scoville) <= 1000000
#     0 <= K <= 1000000000
#     scoville의 원소는 각각 0 이상 1000000 이하
#     모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우 -1 리턴
    
#     제일 작은 값 + (두 번째로 작은 값 * 2)
#     제일 작은 값이 K 이상이 될 때 까지 반복
#     반복한 횟수 체크
#     Min Heap 사용?
    
#     음식 종류가 두 개만 남았는데 합쳤을 때 K를 못 넘는 경우 -1 리턴
    
#     일단 무식하게 Min Heap 만들어보자
    
    heap = Heap()
    for x in scoville:
        heap.insert(x)
        
    answer = 0
    while heap.peek() < K:
        if len(heap.heap_arr) == 3 and (heap.heap_arr[1] + (heap.heap_arr[2] * 2) < K):
            return -1
        first = heap.pop()
        second = heap.pop()
        fusion = first + (second * 2)
        heap.insert(fusion)
        answer += 1
    
    return answer

class Heap:
    def __init__(self):
        self.heap_arr = list()
        self.heap_arr.append(None)

    def peek(self):
        return self.heap_arr[1]
        
    def move_up(self, inserted_idx):
        if inserted_idx <= 1:
            return False
        parent_idx = inserted_idx // 2
        if self.heap_arr[parent_idx] > self.heap_arr[inserted_idx]:
            return True
        else:
            return False
        
    def insert(self, data):
        self.heap_arr.append(data)
        
        inserted_idx = len(self.heap_arr) - 1
        while self.move_up(inserted_idx):
            parent_idx = inserted_idx // 2
            if self.heap_arr[parent_idx] > self.heap_arr[inserted_idx]:
                self.heap_arr[parent_idx], self.heap_arr[inserted_idx] = self.heap_arr[inserted_idx], self.heap_arr[parent_idx]
                parent_idx = inserted_idx
        return True
    
    def move_down(self, popped_idx):
        left_child_idx = popped_idx * 2
        right_child_idx = popped_idx * 2 + 1
        
        if left_child_idx >= len(self.heap_arr):  # 왼쪽이 없으면 오른쪽도 없음
            return False
        elif right_child_idx >= len(self.heap_arr):  # 오른쪽만 없음
            if self.heap_arr[left_child_idx] < self.heap_arr[popped_idx]:
                return True
            else:
                return False
        else:
            if self.heap_arr[left_child_idx] > self.heap_arr[right_child_idx]:
                if self.heap_arr[popped_idx] > self.heap_arr[right_child_idx]:
                    return True
                else:
                    return False
            else:
                if self.heap_arr[popped_idx] > self.heap_arr[left_child_idx]:
                    return True
                else:
                    return False
                
    def pop(self):
        return_data = self.heap_arr[1]
        self.heap_arr[1] = self.heap_arr[-1]
        del self.heap_arr[-1]
        popped_idx = 1
        
        while self.move_down(popped_idx):
            left_child_idx = popped_idx * 2
            right_child_idx = popped_idx * 2 + 1

            if right_child_idx >= len(self.heap_arr):  # 오른쪽만 없음
                if self.heap_arr[left_child_idx] < self.heap_arr[popped_idx]:
                    self.heap_arr[left_child_idx], self.heap_arr[popped_idx] = self.heap_arr[popped_idx], self.heap_arr[left_child_idx]
                    popped_idx = left_child_idx
            else:
                if self.heap_arr[left_child_idx] > self.heap_arr[right_child_idx]:
                    if self.heap_arr[popped_idx] > self.heap_arr[right_child_idx]:
                        self.heap_arr[popped_idx], self.heap_arr[right_child_idx] = self.heap_arr[right_child_idx], self.heap_arr[popped_idx]
                        popped_idx = right_child_idx
                else:
                    if self.heap_arr[popped_idx] > self.heap_arr[left_child_idx]:
                        self.heap_arr[popped_idx], self.heap_arr[left_child_idx] = self.heap_arr[left_child_idx], self.heap_arr[popped_idx]
                        popped_idx = left_child_idx
        
        return return_data

디버깅을 좀 하고 싶은데 

코드 생긴거도 비슷하고 노트북 화면이 가로가 넘 짧아 제대로 할 수가 없다.. 

 

아무튼 이 이후로 나도 heapq를 써서 풀어봤는데

와 그냥 heapify부터 감탄 나오고 heappush, heappop 하니 원하는대로 쫙

 

import heapq

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

직접 구현에선 index 0에 None을 넣었는데 heapify는 그런거 필요 없어서 사용할 때 잠깐 헤맸음

확실히 코드가 짧아지니까 어디가 잘못됐는지 한 눈에 파악할 수 있어서

while문 안에 모든 음식을 K 이상 맵게 못만들 경우를 깜빡한걸 바로 체크해서 추가했더니 풀이에 성공했다.

 

오늘 하루 배운거로 응용하기엔 좀 빡셌다고 볼 수 있겠는데

나중에 꼭 성장해서 다시 돌아와, 직접 구현하는 방법으로 풀어버릴거임 딱 기다려