algo lev-2 더 맵게 (python)

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

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

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

출처 : 프로그래머스 Level2

내가 푼 풀이

• 마침 어제 공부한 heapq를 활용한 문제라서 좋았다 ♬

• 마지막 케이스 실패.py

  def solution(scoville, K):
      import heapq
      count = 0
      heapq.heapify(scoville)
      while len(scoville) > 1:
          n1 = heapq.heappop(scoville)
          n2 = heapq.heappop(scoville)
          if n1 < K or n2 < K :
              heapq.heappush(scoville, n1+(n2*2))
              count += 1
          else :
              return count
      return -1
  

  • 이전 풀이에서 heapq.heapify(scoville) 를 하지 않았더니 pop() 값들이 올바르게 나오지 않아서 계속 실패했었다
  • 마지막 케이스 통과가 안돼서 여러 테스트 케이스를 다시 고민해봤다

• 성공!!!

  def solution(scoville, K):
      import heapq
      count = 0
      heapq.heapify(scoville)
      while len(scoville) > 1:
          n1 = heapq.heappop(scoville)
          n2 = heapq.heappop(scoville)
          if n1 < K or n2 < K :
              heapq.heappush(scoville, n1+(n2*2))
              count += 1
          else :
              return count
      if scoville[0] > K:
          return count
      else :
          return -1
  

  • 길이가 1이면 빠져나오게 되어 있는데, 처음부터 scoville의 길이가 2인 경우 while문을 돌면 길이가 1이 됨
    • 그럴 경우, 만약 문제의 조건를 만족하더라도 else : return count 조건을 만나지 않고 while문을 빠져나와버려서 count 값이 출력되지 않았다
  • 그래서 if scoville[0] > K 조건을 추가해서 값이 한 개밖에 안남았더라도 문제의 조건에 만족하면 return count 할 수 있도록 만들어 줬다
  • scoville : [1,2] K : 3 , output: 1
    • scoville : [5] , count : 1 인 상태로 while 루프가 종료됨
    • scoville[0] > K 이기 때문에 return count –> 1을 반환

배운 점

pop() 하고 싶으면 먼저 heap으로 만들기!

• heapq.heappop(listA) 할 때, 만약 listA가 온전한 min-heap 구조가 아니면 자동으로 heap으로 만들어 주고, pop()을 하는 줄 알았는데 아니었다
• 그래서 우선 heapq.heapify(listA) 로 listA를 heap 형태로 만들어준 뒤, pop()을 해야 올바른 결과를 얻을 수 있음!!