[프로그래머스, 파이썬] 더 맵게

풀이

• 해당 문제는 heap을 사용해서 푸는 문제이지만
• 사용하지 않고 풀어보려고 했다가 효율성에서 에러가 나는 것을 확인하여 heap을 사용하기로 함
• 우선 heap에 대해 처음 사용하다보니 어떤 경우 사용하는지 알아보니
• 최소,최대 값을 확인할 경우 트리 구조로 찾다보니 빠르게 찾는 것 같다.
• 그래서 heapq을 import 한 다음
• 현재 s로 받아오는 배열을 heapq로 변환한 다음
• heappush로 s 배열에 최소 값인 heappop()과 그 다음 값에 식을 적용하여 추가하기
• 그리고 변경되어진 s의 값 중 가장 작은 값이 K보다 크거나 같다면 return하고
• 만약 s의 길이가 2보다 작다면 더 이상 방법이 없기에 -1로 return하여 해결

 

import heapq

def solution(s, K):

    state = True

    for i in s:

        if K > i:

            state = False

            break

    if state: return 0

    result = 0

    s.sort()

    heapq.heapify(s)

    while len(s) >= 2:

        heapq.heappush(s,heapq.heappop(s)+heapq.heappop(s)*2)

        result += 1

        if s[0] >= K: return result

    return -1