알고리즘 풀이 -3 프로그래머스 heap 문제 "더 맵게"

문제를 푸는데 사용된 아이디어는 간단하다. 

우선 반복문은 scoville의 최솟값이 k 이상이면 멈추게 되고, 가장 작은값과 그 다음 작은 값 * 2 한 값을 배열에 새로 푸시한다. 가장 단순한 접근이 아닐까 싶다. 그리고 주어진 scoville로 k값을 넘지 못할경우 exception을 걸어서 return -1 을 해준다. 

"""프로그래모스 더 맵게 문제 최소 힙 쓰면 풀릴듯 힙은 2진 트리 바탕으로 만드는 자료구조!"""
'''첫 번째 풀이 난 힙같은거 모르겠다!'''
def solution(scoville, K):
    answer = 0
    while min(scoville) < K:
        try:
            idx = scoville.index(min(scoville))
            minScoville = scoville.pop(idx)
            scoville.append(minScoville + 2 * scoville.pop(scoville.index(min(scoville))))
            answer += 1
        except ValueError:
            return -1;
    return answer

solution([1000000000, 200000, 3123123, 9000, 10000, 1200],1000000000)

"""아... 정확도 테스트는 다 통과 했는데 성능 테스트 올 fail"""

결과

정확성 테스트는 모두 통과 했으나 효율성은 꽝.

min 함수가 scoviile의 길이 만큼 반복을 할테니 2*n^2만큼의 반복을 도는 것 같다. 

일단은 조금 수정해봤는데.. 실패 ㅠ 나중에 다시 도전!