Programmers | Level 2 | 더 맵게

Programmers | Level 2 | 더 맵게

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Heap

Description

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶어 합니다. 이를 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 섞어 새로운 음식을 만듭니다. 이때 섞은 음식의 스코빌 지수는 다음과 같이 계산됩니다:

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

모든 음식의 스코빌 지수가 K 이상이 될 때까지 이 과정을 반복합니다. 모든 음식의 스코빌 지수가 K 이상이 될 때까지 섞어야 하는 최소 횟수를 구하세요. 만약 이를 달성할 수 없는 경우 -1을 반환합니다.

Constraints

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.

Examples

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

Solutions

• ⏳ TC: O(n log n)
• 💾 SC: O(n)

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int ele : scoville) heap.add(ele);
        
        int count = 0;
        while (heap.peek() < K) {
            if (heap.size() < 2) {
                count = -1;
                break;
            }
            int first = heap.poll(); // 가장 맵지 않은 음식의 스코빌 지수
            int second = heap.poll(); // 두 번째로 맵지 않은 음식의 스코빌 지수
            heap.add(first + (second * 2)); // 새로운 음식 생성
            count++;
        }
        
        return count;
    }
}

Approaches

이 문제는 주어진 음식들의 스코빌 지수를 효율적으로 처리하기 위해 힙(Heap) 자료구조를 사용하는 것이 핵심인 문제입니다.

힙 자료구조는 완전 이진 트리 구조를 가진 자료구조로, 각 노드는 자식 노드보다 크거나 작은 값을 가지도록 정렬됩니다. 최대 힙(Max Heap)에서는 부모 노드가 자식 노드보다 크거나 같은 구조를 가지며, 루트 노드에는 가장 큰 값이 위치합니다. 반대로, 최소 힙(Min Heap)에서는 부모 노드가 자식 노드보다 작거나 같은 구조를 가지며, 루트 노드에는 가장 작은 값이 위치합니다.

힙에서의 삽입과 삭제 연산은 O(log n)의 시간 복잡도를 가지며, 이러한 연산은 힙의 특성을 유지하기 위해 Heapify 과정을 통해 이루어집니다. 힙은 특히 우선순위 큐를 구현하는 데 자주 사용됩니다.

Java의 PriorityQueue 클래스는 이러한 힙을 기반으로 한 자료구조로, 기본적으로 최소 힙을 구현합니다. 이 클래스는 요소들을 자동으로 오름차순으로 정렬하여 가장 작은 요소가 큐의 맨 앞에 위치하도록 합니다.

이러한 힙 자료구조와 PriorityQueue를 활용하여 다음과 같은 접근 방식을 통해 문제를 해결할 수 있었습니다:

• 힙 초기화: 주어진 scoville 배열의 모든 요소를 PriorityQueue에 삽입하여 최소 힙을 구성합니다. 이를 통해 스코빌 지수가 낮은 음식들이 자동으로 정렬됩니다.
• 음식 섞기 반복: 힙의 루트 노드(최소값)가 목표 스코빌 지수 K 이상이 될 때까지 다음 과정을 반복합니다.
  • 최솟값 추출: PriorityQueue.poll() 메서드를 통해 큐에서 가장 작은 스코빌 지수를 추출합니다.
  • 두 번째 최솟값 추출: 큐에서 두 번째로 작은 스코빌 지수를 같은 방식으로 추출합니다.
  • 새로운 음식 생성: 추출한 두 스코빌 지수를 섞어 새로운 음식을 만듭니다. 새로운 스코빌 지수는 첫 번째 최솟값 + (두 번째 최솟값 * 2)로 계산됩니다.
  • 새로운 음식 삽입: 생성된 음식을 다시 힙에 삽입합니다. PriorityQueue는 새로 추가된 값을 자동으로 내부 힙 구조에 맞게 재정렬하며, 최소값이 루트에 위치하도록 유지합니다.
  • 횟수 카운트: 섞는 작업이 완료될 때마다 count 값을 증가시킵니다.
• 종료 조건 확인 및 결과 반환:
  • 힙의 최소값이 K 이상이 되면 섞은 횟수 count 값을 반환합니다.
  • 만약, 힙에 남아 있는 음식이 2개 미만인데도 모든 음식의 스코빌 지수를 K 이상으로 만들지 못한 경우, -1을 반환합니다.

이러한 접근 방식은 PriorityQueue를 사용하여 매 단계에서 가장 작은 두 스코빌 지수를 효율적으로 관리하고 섞는 작업을 통해 문제를 해결합니다. 전체 알고리즘의 시간 복잡도는 O(n log n)으로, 주어진 문제의 입력 크기에도 충분히 대응할 수 있습니다.