[프로그래머스 | 파이썬3] 더 맵게- 힙 활용

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

코딩테스트 연습 - 더 맵게

> 힙활용

힙을 활용해서 scoville에서 최소값을 뽑아 계산을 수행하도록 했다. 

https://docs.python.org/3/library/heapq.html

heapq — Heap queue algorithm — Python 3.9.6 documentation

https://westshine-data-analysis.tistory.com/44

최단경로 알고리즘(2)/ 힙을 사용한 다익스트라 알고리즘

 

# 1.  맨 마지막 테스트 케이스 통과 X

처음 작성한 코드문은 아래와 같다. 

 

import heapq
def solution(scoville, K):
	# 입력받은 리스트를 힙 자료구조로 변환
    heapq.heapify(scoville) 
    answer=0
    
    # 힙 길이가 1보다 클때 조건문 반복
    while len(scoville)>1:
    
    	# 힙의 최소값이 K 이상이면 모든 값들이 K이상이라는 의미이므로 그대로 answer반환
        first= heapq.heappop(scoville)
        if first >= K:
            return answer
            break
            
        # 두번째 최소값 꺼내고 힙에 두 요소를 계산한 값 추가
        second= heapq.heappop(scoville)
        heapq.heappush(scoville,first+(second*2))
        answer+=1
   # 반복문을 모두 수행하고도 조건에 안맞으면 모든 요소가 K이상이 될 수 없다는 뜻이므로 -1 반환
    return -1

 

그런데 accuracy 맨 마지막 번호에서 에러가 났다. 그 이유는 다음 테스트 케이스 때문인 것으로 생각된다. 

 

scoville= [1,2,3]

K= 9

 

해당 테스트 케이스 일때 첫번째 반복에서 2+1*2= 4가 나와 scoville는 [4,3]이 된다. 두번째 반복에서 4+3*2= 10이 나와 [10]이 된다. 10이 K인 9 이상이므로 조건에 answer값을 도출해야한다. 하지만 첫번째 코드에 의하면 while 조건문에 의해 -1이 반환된다.

이를 해결하기 위해 조건문을 len(scoville) >0으로 바꾸었지만 네개의 테스트 케이스에서 런타임 에러가 났다. 

결과적으로 바꾼 코드는 다음과 같다. 

 

# 2. 통과

 

import heapq
def solution(scoville, K):
    heapq.heapify(scoville) 
    answer=0
    
    while len(scoville)>1:
        first= heapq.heappop(scoville)
        if first >= K:
            return answer
            break
        second= heapq.heappop(scoville)
        heapq.heappush(scoville,first+(second*2))
        answer+=1
    # 이부분 추가   
    if scoville[0]>=K:
        return answer
    else:
        return -1

 

위 예제를 통과할 수 있게끔 1번 코드는 그대로 넣고 while문이 끝났을 때 마지막 남은 하나의 요소가 K이상이면 answer을 반환할 수 있도록 조건문으로 구현하였다. 

 

이렇게 조건문을 추가적으로 넣는다 하더라도 다른 테스트 케이스의 경우 while문의 if문에서 조건을 만족하면 값을 반환하고 함수가 종료되기 때문에 런타임에러가 날 일은 없다고 판단하였다.