[Python 알고리즘] 스코빌 지수

O(logn)·2024년 3월 4일

코테 준비

목록 보기

2/3

문제

문제 설명

열정적인 요리사인 Alex는 모든 손님에게 적절한 매운 맛의 요리를 제공하고자 합니다. Alex는 요리의 매운 맛을 일정 수준 이상으로 조절하기 위해, 매운 맛의 단위를 '매운맛 지수'로 정의하고, 두 가지 요리를 특별한 방식으로 결합하여 새로운 요리를 만드는 방법을 고안했습니다.

결합된 요리의 매운맛 지수 = 가장 덜 매운 요리의 매운맛 지수 + (두 번째로 덜 매운 요리의 매운맛 지수 * 2)

Alex는 모든 요리의 매운맛 지수가 특정 기준치 이상이 될 때까지 요리를 반복하여 결합합니다. Alex가 가진 요리의 매운맛 지수 배열 spiciness와 목표 매운맛 지수 threshold가 주어질 때, 모든 요리의 매운맛 지수를 threshold 이상으로 만들기 위해 결합해야 하는 최소 횟수를 반환하는 combine_min_spicy 함수를 작성해주세요.

제한 사항

spiciness의 길이는 2 이상 1,000,000 이하입니다.
threshold는 0 이상 1,000,000,000 이하입니다.
spiciness의 각 요소는 0 이상 1,000,000 이하입니다.
모든 요리의 매운맛 지수를 threshold 이상으로 만들 수 없는 경우에는 -1을 반환합니다.

입출력 예

spiciness                  threshold  return
[1, 2, 3, 9, 10, 12]       7          2

입출력 예 설명

매운맛 지수가 1인 요리와 2인 요리를 결합하면, 새로운 요리의 매운맛 지수는 1 + (2 * 2) = 5가 됩니다. 이제 가진 요리의 매운맛 지수는 [5, 3, 9, 10, 12]가 됩니다.
매운맛 지수가 3인 요리와 5인 요리를 결합하면, 새로운 요리의 매운맛 지수는 3 + (5 * 2) = 13이 됩니다. 이제 가진 요리의 매운맛 지수는 [13, 9, 10, 12]가 됩니다.
모든 요리의 매운맛 지수가 7 이상이 되었으며, 이때 결합한 횟수는 2회입니다.

오답 풀이 1

def combine_min_spicy(spiciness, threshold):
    answer = 0
    spiciness = sorted(spiciness)
    while spiciness[0] < threshold:
        spiciness[0] = spiciness[0] + spiciness[1] * 2
        spiciness.pop(1)
        spiciness = sorted(spiciness)
        answer += 1
        if sum(spiciness) == 0:
            answer = -1
            break
        
    return answer

heap을 모르고 풀었을 때 효율성 문제와 몇몇 테스트케이스 실패가 떴었다.
아래는 heap 개념을 학습한 뒤 재풀이한 코드이다.

오답 풀이 2

import heapq

def combine_min_spicy_heap(spiciness, threshold):
    if sum(spiciness) == 0:
        return -1
    heapq.heapify(spiciness)
    while spiciness[0] < threshold:
        fst = heapq.heappop(spiciness)
        scn = heapq.heappop(spiciness)
        heapq.heappush(spiciness, fst + scn * 2)
        answer += 1
    return answer

heapq를 적절하게 잘 활용하여 1번 오답에 비해 효율적으로 정렬, 삭제를 했다.
효율성 테스트는 통과하였지만 여전히 오답인 테케가 남아있었다.
gpt의 도움을 받아 코드를 수정하였는데 아래와 같다.

import heapq

def combine_min_spicy_heap(spiciness, threshold):
    if sum(spiciness) == 0 or not spiciness:
        return -1
    heapq.heapify(spiciness)
    answer = 0
    while spiciness[0] < threshold and len(spiciness) > 1:
        fst = heapq.heappop(spiciness)
        scn = heapq.heappop(spiciness)
        heapq.heappush(spiciness, fst + scn * 2)
        answer += 1
    if spiciness[0] < threshold:
        return -1
    return answer

아래는 GPT가 생성한 Test Cases다.

# Test case 1: Simple case where mixing is required
spiciness = [1, 2, 3, 9, 10, 12]
threshold = 7
# Expected outcome: 2
# Explanation: Mix spiciness 1 and 2 (resulting in 5), then mix 3 and 5*2 (resulting in 13), which makes all elements above 7.

# Test case 2: No mixing needed
spiciness = [8, 10, 11]
threshold = 7
# Expected outcome: 0
# Explanation: All spiciness levels are already above 7.

# Test case 3: Edge case with minimum elements
spiciness = [1]
threshold = 100
# Expected outcome: -1
# Explanation: Impossible to reach 100 with only one element.

# Test case 4: Impossible to reach the desired level
spiciness = [1, 2, 2]
threshold = 10
# Expected outcome: -1
# Explanation: Even after mixing, cannot reach spiciness level of 10.

# Test case 5: Large range of spiciness levels
spiciness = [1, 2, 3, 9, 10, 12, 1000, 1200]
threshold = 200
# Expected outcome: 4
# Explanation: Requires several mixes but can achieve the desired level.

# Implementing the function to run these test cases
def run_test_cases():
    test_cases = [
        ([1, 2, 3, 9, 10, 12], 7, 2),
        ([8, 10, 11], 7, 0),
        ([1], 100, -1),
        ([1, 2, 2], 10, -1),
        ([1, 2, 3, 9, 10, 12, 1000, 1200], 200, 4),
    ]

    for i, (spiciness, threshold, expected) in enumerate(test_cases, 1):
        result = combine_min_spicy_heap(spiciness, threshold)
        assert result == expected, f"Test case {i} failed: expected {expected}, got {result}"
        print(f"Test case {i} passed: expected {expected}, got {result}")

run_test_cases()