그리디 + PQ (PRO 광물 캐기)

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

 

import java.util.*;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        int totalPicks = picks[0] + picks[1] + picks[2];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[2] - a[2]);
        // "돌 곡괭이를 썼을 때의 피로도"를 기준으로 내림차순 저장
        // 왜냐하면 돌 곡괭이만 광물 종류를 식별해주고, "어려운 광물이 많은 순서"로 정렬할 수 있기 때문이다.
        // 따라서 PQ에서 뽑는 순서대로 "가장 좋은 곡괭이"부터 사용해 처리한다.
        
        
        // 1. 광물을 5개씩 그룹화해서 피로도를 계산해 PQ에 저장
        for (int i = 0; i < minerals.length; i += 5) {
            if (i / 5 >= totalPicks) {
                break; // 곡괭이가 모자란 경우, 계산 중단
            }
            
            int dia = 0, iron = 0, stone = 0;
            
            // 반복 종점 계산 주의 (마지막 그룹이 5개 미만일 수 있음)
            for (int j = i; j < Math.min(i + 5, minerals.length); j++) { 
                if (minerals[j].equals("diamond")) {
                    dia++; iron += 5; stone += 25;
                } else if (minerals[j].equals("iron")) {
                    dia++; iron++; stone += 5;
                } else {
                    dia++; iron++; stone++;
                }
            }
            pq.offer(new int[]{dia, iron, stone});
        }
        
        
        // 2. "피로도가 높은 광물 그룹"부터 "가장 좋은 곡괭이"로 처리 (=그리디)
        for (int i = 0; i < 3; i++) {
            while (picks[i] > 0 && !pq.isEmpty()) {
                int[] group = pq.poll();
                answer += group[i];
                picks[i]--;
            }
        }
        
        return answer;
    }
}

 

이 코드의 주요 특징과 최적화 포인트는 다음과 같습니다:

1. 그룹화: 광물을 5개씩 그룹화하여 처리합니다. 이는 곡괭이 하나당 최대 5개의 광물을 캘 수 있기 때문입니다.
2. 우선순위 큐 사용: 각 그룹의 "가치"를 계산하여 우선순위 큐에 저장합니다. 가치는 "돌" 곡괭이로 캤을 때의 피로도로 정의됩니다.
3. 그리디 접근: 가장 가치가 높은 그룹부터 처리하며, 가능한 가장 좋은 곡괭이를 사용합니다.
4. 효율적인 계산: 각 그룹에 대해 다이아몬드, 철, 돌 곡괭이로 캤을 때의 피로도를 미리 계산하여 저장합니다.
5. 불필요한 계산 방지: 사용 가능한 곡괭이 수보다 많은 광물 그룹은 무시합니다.

이 방법의 시간 복잡도는 O(n log n)이며, 여기서 n은 광물 그룹의 수입니다. 이는 우선순위 큐의 삽입과 삭제 연산 때문입니다.

이 접근 방식은 모든 가능한 순열을 생성하는 완전 탐색 방법보다 훨씬 효율적이며, 주어진 제한 사항 내에서 최적의 해결책을 제공합니다.