[Python] Programmers lv2 - 더 맵게

[Python] Programmers lv2 - 더 맵게

 

코딩테스트 연습 - 더 맵게 | 프로그래머스 스쿨 (programmers.co.kr)

 

문제 설명

 

문제 설명 이미지

 

• 주어진 조건
  • 음식의 스코빌 지수가 담긴 리스트
  • 스코빌 지수의 최소 요구치
  • 리스트 내의 모든 요소들이 해당 요구치를 넘어야 한다
• 풀이 아이디어(기존)
  • 주어진 스코빌 지수 리스트를 heap에 넣어준다
  • heap으로 들어가면 작은 순서대로 정렬이 되며 pop을 하는 경우에도 작은 순서대로 나오게 된다
  • heap에서 두 개의 원소를 꺼내서 조건에 맞게 조립 후 총 조립 횟수의 cnt와 요구치를 넘었는지 확인한다
• 풀이 아이디어 ( 오답 후 조건 추가 - 문제를 다각도로 분석 및 조건 설정의 미숙함 존재 )
  • 첫 번째 원소를 pop 하고 힙에 남아있는 원소가 있는지 체크하는 부분
    • 해당 원소를 pop을 한다는 것은 리스트에 있는 원소가 요구치를 못 넘었다는 것
  • 조건을 다시 살펴보면 요구치를 넘어야한다는 것이 아닌 요구치 이상이다.
    • '이상' 조건이므로 요구치를 포함해서 결정해야한다
  • while 반복문을 진행하기 이전에 처음부터 주어진 스코빌 리스트가 이미 요구치를 넘긴 경우
    • while 이전에 사전에 첫 번째 원소를 확인하여 k를 넘겼는지 확인

 

풀이 코드

 

import heapq

def solution(sco, k):
    answer = -1
    heap = []
    for i in sco:
        heapq.heappush(heap,i)
    if heap[0] >= k: # 힙의 첫번째 원소를 확인하여 조건을 만족하였는지 확인
        return 0
    cnt = 0 
    while True:
        opt1 = heapq.heappop(heap)
        if not heap:  # 더 이상 조합할 요소가 없다면
            return -1  # 조건을 만족할 수 없으므로 -1 반환
        opt2 = heapq.heappop(heap)
        opt3 = opt1 + opt2 * 2
        heapq.heappush(heap, opt3)
        cnt += 1
        if heap[0] >= k:  # 힙의 최소 요소가 K 이상이면 조건 충족
            return cnt

    return answer  # 모든 조합을 시도했지만 조건을 만족하지 못한 경우