프로그래머스 lv2 광물캐기

문제 링크

광물캐기

풀이

헤딩 문제는 다음과 같이 풀었다.

• 곡괭이의 개수 * 5 만큼 광물 배열의 인덱스를 자른다. 어차피 곡괭이를 다쓰면 더는 못 캔다.
• 남은 광물을 5개 씩 묶어서 각 곡괭이별로 드는 비용을 계산한다. 이걸 배열로 만든다. (ex > new int[]{dia, iron, stone})
• 만든 배열을 다음과 같은 기준으로 정렬한다.
  • stone이 가장 높은걸 맨 처음으로, 같다면 iron이 높은 순, 마지막으로는 dia가 높은순
  • 그 이유는 stone이 다이아몬드를 캘 때 가장 높은 피로도를 소모하기에, 가장 높은 피로도 소모를 하는 광물들을 다이아 곡괭이로 캐야한다.
• 그렇게 정렬한 배열을 돌면서 곡괭이들을 순서대로 넣어가면서 비용을 계산한다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;

        int totalPick = Arrays.stream(picks).sum() * 5;

        if (minerals.length > totalPick) minerals = Arrays.copyOfRange(minerals, 0, totalPick);

        List<int[]> costs = new ArrayList<>();
        int[] cost = new int[3];
        for (int i = 0; i < minerals.length; i++) {
            String mineral = minerals[i];

            if (mineral.equals("diamond")) {
                cost[0] += 1;
                cost[1] += 5;
                cost[2] += 25;
            }

            if (mineral.equals("iron")) {
                cost[0] += 1;
                cost[1] += 1;
                cost[2] += 5;
            }

            if (mineral.equals("stone")) {
                cost[0] += 1;
                cost[1] += 1;
                cost[2] += 1;
            }

            if ((i + 1) % 5 == 0) {
                costs.add(cost);
                cost = new int[3];
            } else if (i == minerals.length - 1) {
                costs.add(cost);
            }
        }


        Collections.sort(costs, (o1, o2) -> {
            if (o1[2] > o2[2]) {
                return -1;
            } else if (o1[2] < o2[2]) {
                return 1;
            } else {
                if (o1[1] > o2[1]) {return -1;}
                else if (o1[1] < o1[1]){ return 1;}
                else {
                    if (o1[0] > o2[0]) {return -1;}
                    else if (o1[0] < o1[0]) {return 1;}
                    else {return 0;}
                }
            }
        });


        for(int i = 0; i < costs.size(); i++){
            if(picks[0] > 0){
                answer += costs.get(i)[0];
                picks[0] -= 1;
            } else if(picks[1] > 0){
                answer+= costs.get(i)[1];
                picks[1] -= 1;
            } else if(picks[2] > 0){
                answer+= costs.get(i)[2];
                picks[2] -= 1;
            } else {
                break;
            }
        }

        return answer;
    }
}

코드가 길어서 다른 사람들은 어떻게 풀었나하고 본 것중에 bfs로 푼 것을 보았다.
깔끔하게 잘 푼 것 같아서 코드를 같이 적어본다.

import java.util.*;

class Solution {
    private int min = Integer.MAX_VALUE;
    private Map<String, List<Integer>> energy;

    public int solution(int[] picks, String[] minerals) {
        energy = new HashMap<>();
        energy.put("diamond", List.of(1, 5, 25));
        energy.put("iron", List.of(1, 1, 5));
        energy.put("stone", List.of(1, 1, 1));
        bfs(0, minerals.length, 0, picks, minerals);
        return min;
    }

    private void bfs(int depth, int mineralCnt, int sum, int[] picks, String[] minerals){
        if (depth == mineralCnt || picks[0] == 0 && picks[1] == 0 && picks[2] == 0) {
            min = Math.min(min, sum);
            return;
        }

        for (int i = 0; i < 3; i++) {
            if (picks[i] == 0) {continue;}
            picks[i]--;
            int temp = 0;
            int nextIdx = Math.min(depth + 5, mineralCnt);
            for (int j = depth; j < nextIdx; j++) {
                temp += energy.get(minerals[j]).get(i);
            }
            bfs(nextIdx, mineralCnt, sum + temp, new int[]{picks[0], picks[1], picks[2]}, minerals);
            picks[i]++;
        }
    }
}