프로그래머스 - 광물 캐기

프로그래머스 - 광물 캐기

광물의 순서를 담은 array인 minerals와 곡괭이의 종류를 담은 array picks가 주어집니다. 곡괭이와 캐낼 광물의 조합에 따른 피로도가 정해져 있을 때, 최대한 많은 광물을 캐는 최소한의 피로도를 구하는 문제입니다.

힘든 광물을 캐려 할수록 좋은 곡괭이를 써야 하기 때문에 greedy로 풀었습니다. 곡괭이 개수 * 5만큼 광물을 캘 수 있기 때문에 minerals를 5개씩 끊어, stone pick 기준 피로도의 array인 fatigues를 만들었습니다. fatigues를 정렬해서 높은 곳부터 diamond, iron, stone 순으로 곡괭이를 쓰면 됩니다.

1. 광물을 다 캐기에 곡괭이가 모자를 수 있으므로, workLen을 구해서 채굴 가능한 지점까지만 fatigues를 만듭니다. 전체 다 만들어버리면 정렬 과정에서 섞이기 때문입니다.

2. fatigues를 만드는 과정에서 diamond에 25를 곱하지 않고 100을, iron에 5를 곱하지 않고 10을 곱했습니다. 그 이유는, 광물을 다 캘 수 있는 만큼 곡괭이를 가지고 있는 상황에 있습니다. minerals를 5개씩 끊어 묶을 때, 마지막 묶음이 {"iron", "iron", "iron", "iron", "iron"}인 경우와 {"diamond"}인 경우처럼 stone pick 기준 피로도가 같은 경우를 구별하기 위함입니다. 5개씩 묶어야 하는데 피로도끼리 5의 배수라서 10을 곱해 회피했습니다.

import java.util.*;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        int pickHave = picks[0] + picks[1] + picks[2];
        int len = minerals.length;
        
        int pickNeed = len / 5;
        if (len % 5 != 0) {
            pickNeed++;
        }
        
        int workLen = Math.min(pickHave, pickNeed);
        int[] fatigues = new int[workLen];
        
        for (int i = 0; i < fatigues.length; i++) {
            int fatigue = 0;
            
            for (int j = 0; j < 5 && i * 5 + j < len; j++) {
                if (minerals[i * 5 + j].equals("diamond")) {
                    fatigue += 100;
                }
                if (minerals[i * 5 + j].equals("iron")) {
                    fatigue += 10;
                }
                if (minerals[i * 5 + j].equals("stone")) {
                    fatigue += 1;
                }
            }
            
            fatigues[i] = fatigue;
        }
        
        Arrays.sort(fatigues);
        
        int cnt = 1;
        for (int i = 0; i < picks.length; i++) {
            for (int j = 0; j < picks[i]; j++) {
                if (cnt > workLen) {
                    break;
                }
                answer += work(i, fatigues[fatigues.length - cnt]);
                cnt++;
            }
        }
        
        return answer;
    }
    
    public int work(int pick, int fatigue) {
        int stone = fatigue % 10;
        int iron = ((fatigue - stone) % 100) / 10;
        int diamond = (fatigue - stone - 10 * iron) / 100;
        
        // diamond pick
        if (pick == 0) {
            return diamond + iron + stone;
        }
        
        // iron pick
        if (pick == 1) {
            return diamond * 5 + iron + stone;
        }
        
        // stone pick
        return diamond * 25 + iron * 5 + stone;
    }
}