[프로그래머스 알고리즘 스터디] 1주차 - 더 맵게

YUZAMIN
YUZAMIN
Hello, World! I'm YUZAMIN, a diligently endeavoring frontend developer 🐤💦
[프로그래머스 알고리즘 스터디] 1주차 - 더 맵게

Summary

문제 설명 📑

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. “ 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) “ Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

제한사항 🚫

scoville의 길이는 1 이상 1,000,000 이하입니다. K는 0 이상 1,000,000,000 이하입니다. scoville의 원소는 각각 0 이상 1,000,000 이하입니다. 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

문제 풀이 👩🏻‍💻

풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# 더 맵게
import heapq


def solution(scoville, K):
    # 스코빌 지수를 담을 heap 선언 후 초기화
    scoville_heap = []
    # 섞어야 하는 최소 횟수를 담을 변수 선언 후 초기화
    answer = 0

    # 스코빌 지수가 담긴 배열을 순회하며 heap에 추가
    # heap에서 스코빌 지수가 오름차순으로 정렬 됨
    for value in scoville:
        heapq.heappush(scoville_heap, value)

    # 가장 작은 스코빌 지수가 K보다 작은 경우 반복
    # 즉, K보다 크지 않은 요소가 존재하는 경우에 계속 반복
    while scoville_heap[0] < K:
        # 만약 스코빌 지수 heap에 남은 요소의 개수가 2개보다 적을 때
        # 즉, 더 이상 섞지 못하고 남은 1개의 요소가 K보다 작은 경우
        # 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우
        # -1을 return
        if len(scoville_heap) < 2:
            return -1

        # 가장 작은 스코빌 지수와 그 다음으로 작은 스코빌 지수를 꺼내어 변수에 할당
        least_scoville = heapq.heappop(scoville_heap)
        second_least_scoville = heapq.heappop(scoville_heap)

        # 두 음식을 섞어서 만든 스코빌 지수를 다시 스코빌 지수 heap에 삽입
        heapq.heappush(scoville_heap, least_scoville +
                       second_least_scoville * 2)

        # 섞은 횟수를 1 증가시킴
        answer += 1

    return answer

문제 출처