프로그래머스 코테고득점kit

힙(Heap) - 더 맵게(level2)

1.문제설명

섞은 음식의 스코빌 지수

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

입출력 예제

2. 해결

MY CODE

=> 42.9 점

def solution(scoville, K):
  count = 0
  while True:
    if len(scoville) == len(list(filter(lambda x: x >= K, scoville))):
      break
    scoville = sorted(scoville[1:])
    scoville[1] = scoville[0] + scoville[1]*2
    count+=1
  return count

=> 57.1 점

def solution(scoville, K):
    init = len(scoville)
    while True:
        if len(scoville) == len(list(filter(lambda x: x >= K, scoville))):
          break
        scoville.sort()
        scoville[1] = scoville[0] + scoville[1]*2
        scoville = scoville[1:]
    return init - len(scoville) 

정확성 테스트에서 런타임에러 와 효율성 테스트에서 시간초과로 실패

3. 개선

무작정 풀어본 풀이였기때문에 힙에 대한 공부를 다시 해본다!
출처 : https://littlefoxdiary.tistory.com/3

힙 (heap)이란?

• 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본

• 힙 property : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다

  • 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
  • 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

이러한 속성으로 인해 힙에서는 가장 낮은(혹은 높은) 우선순위를 가지는 노드가 항상 루트에 오게 되고 이를 이용해 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

( 이때 키 값의 대소 관계는 부모/자식 간에만 성립한다.)

출처 : https://ahribori.com/article/5952f94f22eced098cbd8e3c

파이썬 heapq 모듈은 heapq (priority queue) 알고리즘을 제공한다.

모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리(binary tree) 구조인데, 내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2) 보다 작거나 같은 최소 힙의 형태로 정렬된다.

heapq는 내장 모듈로 별도의 설치 작업 없이 바로 사용할 수 있다.

heapq.heappush(heap, item) : item을 heap에 추가
heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨.
heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )

개선한 코드 => 76.2점

import heapq
def solution(scoville, K):
  heapq.heapify(scoville) 
  count = 0
  while len(scoville) >= 2 : #IndexError 방지
      min = heapq.heappop(scoville) 
 	  #  최솟값이 K보다 크다는 조건 만족(= 종료)
      if min >= K:
        return count
      # 두 번째로 작은 값 가져와서 합친 값을 힙에 삽입
	  else: 
        min2 = heapq.heappop(scoville) 
        heapq.heappush(scoville, min + min2*2)
        count+=1

효율성테스트는 만족했지만 정확성테스트에서 감점이 있다.

발견..! 마지막 제한사항을 고려를 안 했구나
모든 음식의 스코빌 지수를 K이상으로 만들수 없는 경우는 -1를 return 해야한다.

개선한 코드

import heapq
def solution(scoville, K):
  heapq.heapify(scoville) 
  count = 0
  while len(scoville) >= 2 : #IndexError 방지
      min = heapq.heappop(scoville) 
 	  #  최솟값이 K보다 크다는 조건 만족(= 종료)
      if min >= K:
        return count
      # 두 번째로 작은 값 가져와서 합친 값을 힙에 삽입
	  else: 
        min2 = heapq.heappop(scoville) 
        heapq.heappush(scoville, min + min2*2)
        count+=1
   return -1

return -1을 추가하였지만 테스트16에서만 실패가 나왔다.

문제점 발견
scoville이 [6,7]이고 K=7이라면
섞은 음식의 스코빌 지수는 [20]이 된다. 20 >= 7 이고 이때 count=1이기 때문에 return 1이 되어야 하지만 나의 코드에서는 길이가 1이므로 return -1이 된다. 조건의 순서를 변경해야겠다.

최종코드

import heapq
def solution(scoville, K):
  heapq.heapify(scoville) 
  count = 0
  while scoville[0] < K : 
    if len(scoville) < 2 : return -1
    min1 = heapq.heappop(scoville)
    min2 = heapq.heappop(scoville) 
    heapq.heappush(scoville, min1 + (min2*2))
    count+=1     
  return count
  # min은 python의 예약어기때문에 변수명으로 적절하지 않아 변경하였다.