[프로그래머스 level2] 광물 캐기 자바 DFS / greedy 방식

프로그래머스 광물캐기 문제

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

프로그래머스

문제

@param picks [dia , iron, stone] 종류별 곡괭이 수

@param minerals [diamond, iron, stone] 으로 구성된 배열.

@return 채굴완료에 필요한 최소 피로도

접근 & 피드백

어떤 곡괭이를 차용하느냐에 따라 피로도가 다름. 곡괭이 순서를 조합하여 최소값을 구해야 하므로
DFS방식이나 GREEDY 정렬 방식을 사용할 수 있다고 한다.

 

1. DFS방식

// 1. picks = {dia, iron, stone} 곡괭이 수
    // 2. 광물을 5개씩 묶어서 블록으로 만든다
    // 3. 각 블록에 대한 피로도를 3종류 곡괭이로 미리 계산한다
    // 4. DFS로 곡괭이 순서를 조합하며 최소 피로도 갱신
    List<int[]> fatigueBlocks = new ArrayList<>();
    int minFatigue = Integer.MAX_VALUE;

    public int solution(int[] picks, String[] minerals) {
        //각 곡괭이는 광물을 채집할 때 다음과 같은 피로도를 소모한다.
        /*
        다이아 ->  : 다이아,철,돌 = 1
        철 -> : 다이아 = 5, 철, 돌 = 1
        돌 -> : 다이아 = 25, 철 = 5, 돌 = 1
         */
        //모든 곡괭이는 광물 5개 채굴 후 파괴됨.
        for(int i = 0; i < Math.min(minerals.length, (picks[0] + picks[1] + picks[2]) * 5); i += 5){
            int[] fatigue = new int[3];
            for(int j = i; j < i + 5 && j < minerals.length; j++){
                String m = minerals[j];
                fatigue[0] += 1; //다이아 곡괭이
                fatigue[1] += m.equals("diamond") ? 5 : 1; //철 곡괭이
                fatigue[2] += m.equals("diamond") ? 25 : m.equals("iron") ? 5 : 1; //돌 곡괭이
            }
            fatigueBlocks.add(fatigue);
        }

        // 2. DFS 시작
        dfs(0, picks[0], picks[1], picks[2], 0);


        return minFatigue;
    }

    void dfs(int idx, int d, int i, int s, int fatigueSum) {
        if (idx == fatigueBlocks.size()) {
            minFatigue = Math.min(minFatigue, fatigueSum);
            return;
        }
        if (d > 0) dfs(idx + 1, d - 1, i, s, fatigueSum + fatigueBlocks.get(idx)[0]);
        if (i > 0) dfs(idx + 1, d, i - 1, s, fatigueSum + fatigueBlocks.get(idx)[1]);
        if (s > 0) dfs(idx + 1, d, i, s - 1, fatigueSum + fatigueBlocks.get(idx)[2]);
    }

 

2.GREEDY 정렬방식

public int solution2(int[] picks, String[] minerals) {
        int pickCount = picks[0] + picks[1] + picks[2];
        int blockCount = Math.min(minerals.length / 5 + (minerals.length % 5 == 0 ? 0 : 1), pickCount);

        List<int[]> fbs = new ArrayList<>();
        for (int i = 0; i < blockCount; i++) {
            int[] fatigue = new int[3]; // [dia, iron, stone]
            for (int j = i * 5; j < i * 5 + 5 && j < minerals.length; j++) {
                String m = minerals[j];
                fatigue[0] += 1;
                fatigue[1] += m.equals("diamond") ? 5 : 1;
                fatigue[2] += m.equals("diamond") ? 25 : m.equals("iron") ? 5 : 1;
            }
            fbs.add(fatigue);
        }

        // 돌곡괭이 기준 피로도 내림차순 정렬
        fbs.sort((a, b) -> b[2] - a[2]);

        int fatigueSum = 0;
        int blockIdx = 0;

        // 좋은 곡괭이부터 사용
        for (int i = 0; i < picks.length; i++) {
            for (int j = 0; j < picks[i]; j++) {
                if (blockIdx >= fbs.size()) break;
                fatigueSum += fbs.get(blockIdx++)[i]; // i는 곡괭이 종류 index
            }
        }

        return fatigueSum;
    }