프로그래머스 - 더 맵게

문제

더 맵게

힙

자료구조 힙 이용
-> python에 heapq 모듈 있음

힙 생성

• 빈 배열 []로 초기화된 리스트 사용
• heapify()로 원래 만들어놓은 리스트를 힙으로 변환시키기

힙 함수

• heapify(x)
  리스트 x를 선형 시간으로 제자리에서 힙으로 변환함
• heappush(heap,item)
  힙 불변성을 유지하면서 item값을 heap으로 푸시
• heappop(heap)
  힙 불변성을 유지하면서 heap에서 가장 작은 값을 팝하고 반환함.
  힙이 비어있으면 IndecError발생
• heappushpop(heap,item)
  item을 푸시한 다음에 가장 작은 항목을 팝하고 반환함
  heqppush() -> heappop() 보다 heappushpop()이 효율적임
• heapreplace(heap,item)
  heap에서 가장 작은 항목을 팝하고 반환하며 새로운 item도 푸시함
  힙의 크기는 변하지 않음
  heqppop() -> heqppush() 보다 heapreplace()이 효율적임
• 그외: merge,nlargest,nsmallest (참고)

풀이

1. 맨 처음 풀이

def solution(scoville,K):
	answer=0
    while scoville:
    	scoville.sort()
        if scoville[0]>=K:
        	return answer
        one=scoville.pop(0)
        two=scoville.pop(0)
        new=one+two*2
        scoville.append(new)
        answer+=1
    return -1

효율성, 테스트 케이스 1,3,8,14번 실패(런타임오류)
-> 힙을 사용하기로 함

2. 두번째 풀이

from heapq import *

def solution(scoville,K):
    answer=0
    heapify(scoville)
    while scoville:
        print(scoville)
        if scoville[0]>=K:
            return answer
        one=heappop(scoville)
        two=heappop(scoville)
        new=one+two*2
        heappush(scoville,new)
        answer+=1     
    return -1
print(solution([1,2],7))

테스트 케이스 1,3,8,14번 오류
-> solution([1],2) 또는 solution([1,2],7) 과 같은 예시를 돌려보면 IndexError가 생기는 것을 알 수 있음
만약에 스코빌의 길이가 1인데 K값을 안넘어도 heappop()을 수행하기 때문에 IndexError가 발생
따라서, 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우에는 -1 return이라는 조건을 무시한게 됨

3. 마지막

from heapq import *

def solution(scoville,K):
    answer=0
    # 스코빌을 힙으로 만들기
    heapify(scoville)
    # 스코빌 힙에 값이 있을 떄까지
    while scoville:
    	# 제일 덜 매운게 K 넘으면 끝
        if scoville[0]>=K:
            return answer
        # scoville에 값이 하난데, K 안넘으면 다 못넘는거니까
        if len(scoville)==1:
            if scoville[0]<=K:
                return -1
        one=heappop(scoville)
        two=heappop(scoville)
        new=one+two*2
       	# 계산해준 값 스코빌에 넣기
        heappush(scoville,new)
        answer+=1     
    return -1

테스트 케이스 1,3,8,14번이 통과