[프로그래머스 Programmers][Python] 더 맵게

문제 : https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게 | 프로그래머스

이 문제는 힙을 쓰면 간단하게 해결된다.

문제에서

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

를 계속 계산하면 되는 문제라 힙을 쓰면 간단하게 해결된다.

 

1. 일단 scorville 값들을 heap에 넣는다. 이 힙을 s라 한다.
2. s 의 길이가 1개 이상일 동안
   1. 앞에서 두개를 뽑는다, 자동으로 작은값 2개가 나온다.
   2. 그 다음에 문제에 나온대로 a+b*2 (a = 가장 작은값, b = 두번째로 작은값) 를 구해서 다시 s에 넣는다.
   3. answer에 1을 더한다
   4. 힙은 리스트처럼 접근도 가능하므로, 가장 앞 s[0]을 peek 같이 접근해서, K보다 크면 answer를 반환한다.
3. 아까 s 길이 조건으로 while문을 돌리는데, 이 while이 실패한다 == 아무리 문제대로 섞어도 K 이상이 안나온다 라는 뜻이므로
   1. -1을 반환한다. 실패 조건이다.

스택, 힙, 등등 온갖 자료구조 다 구현해놓은 파이썬은 진짜 코딩테스트용으로 최고다.

 

import heapq


def solution(scoville, K):
    s = scoville
    heapq.heapify(s)
    answer = 0
    while len(s)>1:
  

        a = heapq.heappop(s)
        b = heapq.heappop(s)

        heapq.heappush(s,a+b*2)
        answer+=1
        if s[0] >=K:
            return answer


    return -1