광물의 순서를 담은 array인 minerals
와 곡괭이의 종류를 담은 array picks
가 주어집니다. 곡괭이와 캐낼 광물의 조합에 따른 피로도가 정해져 있을 때, 최대한 많은 광물을 캐는 최소한의 피로도를 구하는 문제입니다.
힘든 광물을 캐려 할수록 좋은 곡괭이를 써야 하기 때문에 greedy
로 풀었습니다. 곡괭이 개수 * 5
만큼 광물을 캘 수 있기 때문에 minerals
를 5개씩 끊어, stone pick
기준 피로도의 array인 fatigues
를 만들었습니다. fatigues
를 정렬해서 높은 곳부터 diamond, iron, stone 순으로 곡괭이를 쓰면 됩니다.
workLen
을 구해서 채굴 가능한 지점까지만 fatigues
를 만듭니다. 전체 다 만들어버리면 정렬 과정에서 섞이기 때문입니다.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;
}
}