[프로그래머스] 자바(Java) - 더 맵게

🧩 문제

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

프로그래머스

 

💡 내가 작성한 코드

• 각 단계에서 두개의 가장 작은 스코빌 지수를 찾아서 섞어야 합니다.
• 섞은 후 두개의 가장 작은 스코빌 지수는 제거하고 새로운 스코빌 지수를 다시 추가해야 합니다.
• 이러한 과정을 반복해야 하기 때문에, 리스트에서 최소값을 효율적으로 찾아 제거하고 새로운 값을 삽입하는 작업이 필요합니다.
• 힙 자료구조는 리스트에서 최소값 또는 최대값을 빠르게 찾고 제거할 수 있는 자료구조입니다. 최소 힙을 사용하면 항상 루트 노드에 최소값이 위치하며, 삽입과 삭제 연산의 시간 복잡도가 O(log⁡N)입니다.
• 이 문제에서는 최소 힙을 사용하여 각 단계에서 두 개의 가장 작은 스코빌 지수를 효율적으로 찾아 제거하고, 새로운 스코빌 지수를 삽입함으로써 문제를 해결할 수 있습니다.

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int num : scoville) {
            pq.add(num);
        }
        
        while(K > pq.peek()) {
            if (pq.size() < 2) return -1;
            pq.add(pq.poll() + pq.poll() * 2);
            answer++;
        }
        return answer;
    }
}

• 최소 힙을 구현하기 위해 `PriorityQueue()` 선언
  • 최소 힙을 구현하기 위해 `scoville[]` 을 `PriorityQueue()` 에 추가

 

• 가장 작은 스코빌 지수가 `K` 보다 작은 동안만 반복문 실행
  • `pq.peek()`은 PriorityQueue의 루트 노드 값을 반환
  • 즉, 가장 작은 스코빌 지수(= 루트 노드 값)를 반환

 

• 스코빌 지수 제거 및 추가하기
  • `pq.size() < 2` 조건을 통해 스코빌 지수를 두 개 이상 섞을 수 없는 경우(우선순위 큐에 담겨있는 원소가 1개 이하일 경우), 즉 모든 음식을 K 이상으로 만들 수 없는 경우 -1을 반환 (문제에서 주어진 조건)
  • `pq.poll()`을 두 번 호출하여 두 개의 가장 작은 스코빌 지수를 꺼낸 후
  • 문제에서 주어진 식을 토대로 새로운 스코빌 지수를 계산하여 `pq.add()`를 통해 우선순위 큐에 추가

 

🧠 배운 점

• 우선순위 큐란?
  • 각 요소가 우선순위를 가지고 있으며, 높은 우선순위를 가진 요소가 먼저 처리되는 자료구조
  • 자바에서는 `PriorityQueue` 를 사용하여 우선순위 큐를 구현할 수 있음
  • 기본적으로 `PriorityQueue`는 최소 힙으로 구현되며, 가장 작은 요소가 먼저 처리됨
  • 가장 작은 또는 가장 큰 요소를 빠르게 찾을 수 있고 삽입과 삭제 연산의 시간 복잡도는 O(logN) 이다.