(Week1)[Heap] 더 맵게

주간 코딩스터디 때 푼 문제들을 정리하고 있습니다. 구체적인 문제에 대한 정보는 게시글 내 링크를 살펴봐주세요

소요시간: 20분

1. 문제 설명

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

코딩테스트 연습 - 더 맵게

모든 음식의 스코빌 지수를 K이상으로 만들기 위해 음식을 섞으려고 할 때, 최소 횟수를 구하는 문제

2. 접근 방식

• 문제에서 주어진 리스트의 길이가 2 이상 1,000,000이하로 주어지기 때문에  시간 복잡도가 있을 것이라고 생각
• 주어진 리스트가 매번 순서대로 정렬되어야 한다는 점에서 heap을 사용하기로 함.

3. 코드

import heapq

def solution(scoville, K):
    heap_ls, count = [], 0
    for i in scoville:
        heapq.heappush(heap_ls, i)
    while heap_ls:
        node = heapq.heappop(heap_ls)
        if node > K or len(heap_ls) == 0:
            break
        next_node = heapq.heappop(heap_ls)
        mul_scov = node + (next_node*2)
        heapq.heappush(heap_ls, mul_scov)
        count +=1
    return count if node > K else -1

4. 코멘트

• Heapq를 활용해 Heap을 구현하는데, 오랜만에 사용하다보니 사용법에 익숙하지 않아서다시 한 번 검색했었다. Heapq는 리스트를 생성하고, heapq.heappush와 heapq.heappop으로 입력과 출력을 진행한다.