[프로그래머스] 광물 캐기 - java

나의 풀이

import java.util.*;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        int[][] weights = {{1,1,1},{5,1,1},{25,5,1}};
        int answer = 0;
        int pickCnt = Arrays.stream(picks).sum();
        // 광물을 5개씩 묶은 그룹들을 각 그룹의 광물의 가중치 합의 내림차순에 따라 정렬한 큐
        // 다이아몬드->1 철->5 돌->25
        PriorityQueue<Group> groups = new PriorityQueue<>(Collections.reverseOrder()); 
        for(int i=0; i<minerals.length; i+=5){
            Group g = new Group();
            g.list = new ArrayList<Integer>();
            for(int j=i; j<(i+5); j++){
                if (j>= minerals.length)    break;
                if (minerals[j].equals("diamond"))  {
                    g.list.add(0); // 다이아몬드 광물
                    g.total += 25;
                }
                else if(minerals[j].equals("iron")) {
                    g.list.add(1); // 철 광물
                    g.total += 5;
                }
                else {
                    g.list.add(2); // 돌 광물
                    g.total += 1;
                }
            }
            groups.add(g);
            if (groups.size() == pickCnt)   break; // 곡괭이 개수만큼 그룹을 만들었다면, 이후의 미네랄에 대해서는 캘 수 없다.
        }
        while(!groups.isEmpty()){
            Group g = groups.poll();
            int pick;
            if (picks[0] > 0){ // 다이아몬드 곡괭이 사용
                picks[0]--;
                pick = 0;
            }
            else if (picks[1] > 0){ // 철 곡괭이 사용
                picks[1]--;
                pick = 1;
            }
            else if (picks[2] > 0){ // 돌 곡괭이 사용
                picks[2]--;
                pick = 2;
            }
            for(int m : g.list){
                answer += weights[pick][m];
            }
        }
        return answer;
    }
    static class Group implements Comparable<Group>{
        int total;
        ArrayList<Integer> list;
        
        @Override
        public int compareTo(Group g){
            return this.total - g.total;
        }
    }
}

 

처음에 DFS, 완전탐색을 생각했지만 곡괭이 개수가 최대 15개까지 나올 수 있으므로, 시간이 너무 오래걸릴 것으로 판단했다.

따라서 문제를 다시 읽어보니, 다음과 같은 규칙을 찾을 수 있었다.

돌 광물은 어떤 곡쾡이로 캐더라도 1의 피로도가 누적되며,

철 광물은 돌로 캘때만 5의 피로도가 누적되고,

다이아몬드 광물은 철로 캘때는 5, 돌로 캘때는 25의 피로도가 누적되므로 가장 큰 피로도의 주범이 된다.

즉, 어떤 곡쾡이로 캐더라도 항상 [다이아몬드 >= 철 >= 돌] 의 피로도가 발생한다.

따라서 광물을 5개씩 묶은 그룹별로 가중치를 부여한다음, 각 그룹을 내림차순 정렬하여 가장 가중치가 큰 그룹부터 다이아몬드 곡쾡이 -> 철 곡쾡이 -> 돌 곡쾡이로 캔다면 그리디하게  풀 수 있을 것으로 판단했다.

 

 ** 이때 주의할점이 있다! 이 부분을 놓쳐서 8번 테스트케이스에서 실패했음

그룹별로 내림차순 해서 정렬해서 푼다면, 광물의 순서를 무시하는 셈이 된다.

즉, 실제라면 곡쾡이를 다 쓰고 난 후의 그룹에 있는 미네랄은 캘 수 없지만, 그룹을 내림차순 정렬한 경우에는

해당 그룹의 가중치가 높아 먼저 캘 가능성도 생기는 것이다.

따라서 그룹을 생성할 때, 그룹 개수가 곡쾡이의 개수가 된 경우에는, 더 이상 그룹을 만들지 않는다!!!

 

 

정리하자면, 문제 풀이 순서는 다음과 같다.

1. 5개씩 광물 그룹 만들고, 가중치 계산하기. 곡쾡이 개수만큼만 그룹을 만듦.

2. PriorityQueue에 들어있는 그룹을 한 개씩 poll 해서, 실제 피로도 계산하기. 다이아몬드 곡쾡이가 남아있다면, 우선으로 사용하고, 다 썼다면 철 곡쾡이를, 그마저도 다썼다면 돌 곡쾡이를 사용한다.