프로그래머스 더 맵게(python)

코딩테스트 연습 - 더 맵게

코딩테스트 연습 - 더 맵게

평소에 풀던 방식대로 sort()로 정렬을 하는 방식으로 문제를 풀었더니 효율성 테스트에서 오류가 났다. 문제 유형을 보니 힙이라고 적혀있어서 힙을 이용해야겠다고 생각했다. 파이썬에서 heapq 라는 모듈을 지원해주는 것을 알게 되었고 heapq를 이용하여 문제를 해결했다.

[파이썬] heapq 모듈 사용법

[파이썬] heapq 모듈 사용법

위 블로그를 참고하여 heapq에 대해 배웠다.

해결방법

1. heapq 를 import 한 후 scoville 리스트를 힙큐로 변환

2. scoville 길이가 1이 될때까지 반복

   1. 미리 저장해둔 변수 ans 에 1씩더해줌
   2. heappop을 이용해 가장 적은 값을 삭제하면서 임시값temp에 더하여 스코빌 지수를 계산하고 다시 heapq에 추가
   3. 만약 K보다 scoville[0] 이 작다면 return ans

3. 반복문 탈출 시 -1 리턴

풀이코드

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