[heap 정렬에 관하여] 코딩테스트 연습 힙(Heap) 더 맵게

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

프로그래머스

Solution

import heapq

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

 

음식의 스코빌 지수를 K 이상으로 만들기 위해 가장 낮은 두 개의 음식을 섞는 방법을 사용한다. 섞은 음식의 스코빌 지수는 가장 맵지 않은 음식의 스코빌 지수와 두 번째로 맵지 않은 음식의 스코빌 지수의 조합으로 계산된다. 이를 반복하여 모든 음식의 스코빌 지수를 K 이상으로 만들어야 한다. 만약 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 반환한다.

처음 이 문제를 봤을 때 정답률에 비해 문제가 정말 쉬워 효율성 테스트에서 무조건 통과 못하겠구나 싶었는데 역시나였다. 기본적인 정렬 알고리즘을 써서는 절대 못푸는 문제였고, 출제자도 반드시 파이썬에서 구현하지 못하는 새로운 정렬 알고리즘을 쓰길 원하는 느낌이었다. 답은 gpt에게 물어봐서 풀었고, heapq를 가져와서 풀었다. 혹시나 이 방법을 제하고 풀 수 있는지 물어봤는데, 구글에 이렇게 푼 사람들이 없는지 전혀 엉뚱한 답을 내놓았다. 즉, heapq 안쓰면 못 푸는 문제였다.

 

간단하게 heap 알고리즘을 공부했는데, heap은 이진탐색 구조를 가지고, 일반적인 정렬의 시간 복잡도가 n이라면, heap의 시간 복잡도는 log(n)이라고 한다. 왜냐하면 이진탐색으로 정렬이 미리 되있는 상태에서 절반씩 비교해나가면서 정렬을하기 때문이다.

아래는 이 heapq를 어떤식으로 활용해야하는지 간단한 정리를 해보았다.

import heapq as hq
a = [5,4,1,2,3]
hq.heapify(a) #a를 heap으로 변경, 자동으로 정렬됨
hq.heappop(a) #a의 가장 작은 값을 반환
hq.heappush(a, 6) #a에 6을 넣고 자동으로 정렬 

Attempt 1

def solution(scoville, K):
    answer = 0
    scoville.sort(reverse = True)
    # print(scoville)
    
    while True:
        if scoville[-1] < K and len(scoville) == 1:
            return -1
        if scoville[-1] >= K:
            break
        
        a = scoville.pop()
        b = scoville.pop()
        scoville.append(a+b*2)
        
        answer +=1
        scoville.sort(reverse = True)
    
    return answer

 

Attempt 2

def solution(scoville, K):
    answer = 0
    scoville.sort(reverse = True)
    # print(scoville)
    
    while True:
        if scoville[-1] < K and len(scoville) == 1:
            return -1
        if scoville[-1] >= K:
            break
        
        a = scoville.pop()
        b = scoville.pop()
        
        temp = [a+b*2]
        
        while True:
            
            if scoville == []:
                scoville= temp
                break
            
            if scoville[-1] >= a+b*2:
                scoville.extend(temp)
                break
            
            if scoville[-1] < a+b*2:
                temp.append(scoville.pop())
        
        answer +=1
        scoville.sort(reverse = True)
    
    return answer