마인은 곡괭이로 광산에서 광석을 캐려고 합니다. 마인은 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이를 각각 0개에서 5개까지 가지고 있으며, 곡괭이로 광물을 캘 때는 피로도가 소모됩니다. 각 곡괭이로 광물을 캘 때의 피로도는 아래 표와 같습니다.
예를 들어, 철 곡괭이는 다이아몬드를 캘 때 피로도 5가 소모되며, 철과 돌을 캘때는 피로도가 1씩 소모됩니다. 각 곡괭이는 종류에 상관없이 광물 5개를 캔 후에는 더 이상 사용할 수 없습니다.
마인은 다음과 같은 규칙을 지키면서 최소한의 피로도로 광물을 캐려고 합니다.
즉, 곡괭이를 하나 선택해서 광물 5개를 연속으로 캐고, 다음 곡괭이를 선택해서 광물 5개를 연속으로 캐는 과정을 반복하며, 더 사용할 곡괭이가 없거나 광산에 있는 모든 광물을 캘 때까지 과정을 반복하면 됩니다.
마인이 갖고 있는 곡괭이의 개수를 나타내는 정수 배열 picks
와 광물들의 순서를 나타내는 문자열 배열 minerals
가 매개변수로 주어질 때, 마인이 작업을 끝내기까지 필요한 최소한의 피로도를 return 하는 solution 함수를 완성해주세요.
picks
는 [dia, iron, stone]과 같은 구조로 이루어져 있습니다.
minerals
의 길이 ≤ 50
minerals
는 다음 3개의 문자열로 이루어져 있으며 각각의 의미는 다음과 같습니다.picks | minerals | result |
---|---|---|
[1, 3, 2] | ["diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"] | 12 |
[0, 1, 1] | ["diamond", "diamond", "diamond", "diamond", "diamond", "iron", "iron", "iron", "iron", "iron", "diamond"] | 50 |
입출력 예 #1
다이아몬드 곡괭이로 앞에 다섯 광물을 캐고 철 곡괭이로 남은 다이아몬드, 철, 돌을 1개씩 캐면 12(1 + 1 + 1 + 1+ 1 + 5 + 1 + 1)의 피로도로 캘 수 있으며 이때가 최소값입니다.
입출력 예 #2
철 곡괭이로 다이아몬드 5개를 캐고 돌 곡괭이고 철 5개를 캐면 50의 피로도로 캘 수 있으며, 이때가 최소값입니다.
비용의 최소값을 구하는 문제로 그리디 알고리즘으로 풀 수 있다.
구역을 광물5개 단위로 나눠서 총 비용이 높은구역 부터 좋은 곡괭이를 사용해서 채굴한다.
function solution(picks, minerals) {
const dir = { diamond: [1, 5, 25], iron: [1, 1, 5], stone: [1, 1, 1] };
const pick = [];
const cost = [];
//사용 할 곡괭이를 좋은것부터 차례로 나열한다. 다이아:0 철:1 돌:2
picks.forEach((v, i) => {
if (v) pick.push(...Array.from({ length: v }, () => i));
});
//곡괭이로 캘 수 있는 구역을 5개 단위로 분리해 피로도의 합 계산
for (let i = 0; i < pick.length * 5 && i < minerals.length; i += 5) {
cost.push(
minerals
.slice(i, i + 5)
.reduce((a, c) => a.map((v, i) => v + dir[c][i]), [0, 0, 0])
);
}
//피로도가 높은 구역부터 좋은 곡괭이를 사용해 피로도 합 계산
return cost
.sort((a, b) => b[2] - a[2])
.reduce((a, c, i) => a + c[pick[i]], 0);
}