[프로그래머스] 더 맵게

힙!! 힙은 기억이 안나서... 기초부터 다지고왔다 ^^ ㅎㅎ.. 다음에 풀때도 기억하고 있겠지?.. ㅋ.. 

'힙'으로 푸는 걸 알면 그다지 어렵지 않게 풀 수 있지만.. 이 문제 카테고리가 힙이 아니였으면 ㅎㅎ 난 1년줘도 못풀었을듯^^! 실력 늘리면 이제 뭘로 풀어야될지 바로 알아보겠지?..ㅎ 

 

 

내 코드

def solution(scoville, K):
    import heapq
    
    answer = 0
    heapq.heapify(scoville)
    
    while len(scoville) != 1:
        if scoville[0] >= K:
            return answer
        a = heapq.heappop(scoville)
        b = heapq.heappop(scoville)
        heapq.heappush(scoville,a+(b*2))
        answer+=1
        
    return answer if scoville[0]>=K else -1

'힙'이 최소값과 최대값을 빠른 속도로 가져오는 자료구조이기 때문에 리스트의 최소값 두개를 가져와야하는 이 문제에서는 힙을 써야한다. 

1. scoville 리스트를 heap으로 바꿔준다. 이때 heapify를 사용!

2. heap으로 변환된 scoville에서 heappop을 두번하여 최소값 두개를 a,b에 저장한다.

3. a+b*2를 scoville에 heappush를 사용하여 넣어준다.

4. 만약 scoville의 가장 처음값, 즉 최소값이 K보다 크면 답을 return 한다.

5. 이것을 scoville의 길이가 1보다 클때까지 즉, 2이상일때 까지 반복한다.(heappop을 2번 사용하기 때문에)

6. while문을 빠져나와 만약 scoville의 가장 마지막까지 남은원소(while문이 scoville의 길이가 1이 아닐때까지 반복했으므로 원소는 1개있음), scoville[0]이 K보다 크면 answer반환, 아니면 -1반환

 

 

다른사람 코드

import heapq as hq

def solution(scoville, K):

    hq.heapify(scoville)
    answer = 0
    while True:
        first = hq.heappop(scoville)
        if first >= K:
            break
        if len(scoville) == 0:
            return -1
        second = hq.heappop(scoville)
        hq.heappush(scoville, first + second*2)
        answer += 1  

    return answer

다른사람 코드이다! heappop을 사용하고 K를 비교했다. heappop을 한번 사용한뒤 len의 값을 체크해줬기 때문에 마지막 return문에서 한번 더 if문을 쓸 필요가 없어졌다. 나머지는 나와 같다!

 

 

ㅎㅎ 씨언어로 안하고 파이썬으로 하니까.. 재밌는거같다~~!!! 모듈 좋아~~~~~~