99클럽 코테 스터디_4기 24일차 TIL

TODAY TIL

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 일정 기준 이상으로 만들고 싶어합니다. 이 문제를 해결하기 위해 Python에서 **우선순위 큐(Priority Queue)**를 사용하여 효율적으로 푸는 방법을 소개합니다.

 

문제 설명

Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 아래의 규칙을 사용해 음식을 섞습니다:

1. 스코빌 지수가 가장 낮은 두 개의 음식을 선택합니다.
2. 이 두 음식을 섞어 새로운 음식의 스코빌 지수를 계산합니다: 섞은 음식의 스코빌 지수=가장 낮은 스코빌 지수+(두 번째로 낮은 스코빌 지수×2)\text{섞은 음식의 스코빌 지수} = \text{가장 낮은 스코빌 지수} + (\text{두 번째로 낮은 스코빌 지수} \times 2)섞은 음식의 스코빌 지수=가장 낮은 스코빌 지수+(두 번째로 낮은 스코빌 지수×2)
3. 모든 음식의 스코빌 지수가 K 이상이 될 때까지 위 과정을 반복합니다.

입력 조건:

• scoville: 각 음식의 스코빌 지수가 담긴 배열 (길이: 2 이상 1,000,000 이하).
• K: 목표 스코빌 지수 (0 이상 1,000,000,000 이하).

출력 조건:

• 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 반환합니다.
• 불가능한 경우 -1을 반환합니다.

문제 해결 접근법

이 문제는 최소값과 두 번째 최소값을 반복적으로 선택하는 작업이 필요하므로, **우선순위 큐(Priority Queue)**를 사용하는 것이 효율적입니다. Python에서는 heapq 모듈을 사용해 이를 간단히 구현할 수 있습니다.

 

풀이 과정

1. 힙으로 변환
   • heapq.heapify()를 사용해 입력 배열을 최소 힙으로 변환합니다.
   • 힙 구조를 사용하면 최소값을 빠르게 추출할 수 있습니다.
2. 반복 작업
   • 가장 작은 두 값을 추출하여 새로운 값을 계산합니다.
   • 계산된 값을 다시 힙에 삽입하고, 섞은 횟수를 증가시킵니다.
3. 종료 조건
   • 힙에서 가장 작은 값이 K 이상이면 작업을 종료하고 섞은 횟수를 반환합니다.
   • 힙에 하나의 값만 남았는데도 K 이상이 되지 않으면 불가능하므로 -1을 반환합니다.

Python 코드

import heapq

def solution(scoville, K):
    # 1. 배열을 최소 힙으로 변환
    heapq.heapify(scoville)
    mix_count = 0

    # 2. 반복적으로 가장 작은 두 값을 섞음
    while len(scoville) > 1:
        # 최소 두 개 값을 꺼내 섞기
        first = heapq.heappop(scoville)  # 가장 작은 값
        if first >= K:
            return mix_count  # 모든 값이 K 이상이므로 종료
        second = heapq.heappop(scoville)  # 두 번째로 작은 값
        new_scoville = first + (second * 2)
        heapq.heappush(scoville, new_scoville)  # 섞은 값 삽입
        mix_count += 1

    # 3. 힙에 하나만 남은 경우 확인
    if scoville[0] >= K:
        return mix_count
    else:
        return -1  # 모든 값을 K 이상으로 만들 수 없는 경우

 

예제 실행

입력

scoville = [1, 2, 3, 9, 10, 12]
K = 7

 

실행 과정

1. 초기 힙 구성: [1, 2, 3, 9, 10, 12]
2. 첫 번째 섞기:
   • 선택: 1, 2
   • 새 값: 1 + (2 * 2) = 5
   • 힙 상태: [3, 5, 9, 10, 12]
   • 섞은 횟수: 1
3. 두 번째 섞기:
   • 선택: 3, 5
   • 새 값: 3 + (5 * 2) = 13
   • 힙 상태: [9, 10, 12, 13]
   • 섞은 횟수: 2
4. 세 번째 섞기:
   • 선택: 9, 10
   • 새 값: 9 + (10 * 2) = 29
   • 힙 상태: [12, 13, 29]
   • 섞은 횟수: 3
5. 종료 조건 확인: 힙의 최솟값이 12로 K 이상이므로 종료.

출력

solution(scoville, K)  # 결과: 3

 

결과 및 시간 복잡도 분석

1. 결과: 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 최소 3번 섞어야 합니다.
2. 시간 복잡도:
   • 힙 연산(삽입, 삭제)의 시간 복잡도: O(log⁡N)O(\log N)O(logN)
   • 최대 N번 반복하므로 총 시간 복잡도: O(Nlog⁡N)O(N \log N)O(NlogN)

---

핵심 포인트 정리

• 힙 사용의 효율성: 최소값과 두 번째 최소값을 빠르게 추출하고 삽입.
• 종료 조건의 이해: 모든 값이 K 이상이 되는 순간 종료.
• 예외 처리: 모든 값을 K 이상으로 만들 수 없는 경우 -1 반환.

---

이 풀이를 통해 효율적인 문제 해결 방법과 Python에서 힙을 사용하는 기법을 배울 수 있었습니다. Leo의 매운맛 도전, 이제 여러분도 성공시켜 보세요! 🔥