[Javascript] 프로그래머스 - 광물 캐기

문제 설명

마인은 곡괭이로 광산에서 광물을 캐는 작업을 최소한의 피로도로 수행하려고 합니다. 각 곡괭이는 다이아몬드, 철, 돌로 구성되어 있으며, 광물을 캐는 과정에서 곡괭이의 종류에 따라 피로도가 다르게 소모됩니다.
곡괭이별 광물 채굴 시 피로도는 다음과 같습니다:

곡괭이 종류다이아몬드철돌

다이아몬드	1	1	1
철	5	1	1
돌	25	5	1

각 곡괭이는 종류에 관계없이 광물 5개를 채굴하면 사용할 수 없게 되며, 작업은 다음 규칙을 따릅니다:

1. 사용할 수 있는 곡괭이 중 하나를 선택하여 광물을 캡니다.
2. 한 번 사용한 곡괭이는 5개를 연속으로 채굴한 뒤 더 사용할 수 없습니다.
3. 광물은 주어진 순서대로만 캘 수 있습니다.
4. 모든 광물을 캐거나 사용할 곡괭이가 없을 때까지 작업이 진행됩니다.

마인이 갖고 있는 곡괭이의 개수를 나타내는 배열 picks와 광물들의 순서를 나타내는 배열 minerals가 주어질 때, 작업을 끝내기까지 필요한 최소한의 피로도를 구하는 함수를 작성하세요.

---

제한 사항

1. 곡괭이 수
   • picks는 [다이아몬드, 철, 돌] 곡괭이의 수를 의미하는 배열입니다.
   • 0 ≤ dia, iron, stone ≤ 5
   • 곡괭이는 최소 1개 이상 존재합니다.
2. 광물의 종류
   • minerals는 ["diamond", "iron", "stone"]로 구성된 문자열 배열입니다.
   • 5 ≤ minerals의 길이 ≤ 50

---

해결 방법

• 알고리즘: Greedy Algorithm
  1. 광물 그룹화: 광물을 5개씩 그룹으로 나눕니다. 각 그룹의 가치를 계산해 피로도가 높은 순으로 정렬합니다.
  2. 효율적인 곡괭이 배치: 가치가 높은 그룹부터 가장 효율적인 곡괭이를 사용하여 최소 피로도를 계산합니다.
  3. 피로도 계산: 곡괭이와 광물 종류에 따른 피로도를 누적합니다.

---

시간 복잡도

• 그룹화 및 정렬:
  • 그룹화는 O(N) (광물 배열 길이)
  • 그룹 정렬은 O(G log G) (그룹 개수)
• 최소 피로도 계산:
  • 최대 O(G) (그룹 개수)

최종 시간 복잡도: O(N + G log G),

---

구현 코드

function solution(picks, minerals) {
  let answer = 0;
  const efficiency = [
    [1, 1, 1],
    [1, 1, 5],
    [1, 5, 25],
  ];
  const totalTools = picks.reduce((sum, count) => sum + count, 0);

  let groups = [];
  let groupValue = 0;
  let count = 0;

  for (let i = 0; i < minerals.length && groups.length < totalTools; i++) {
    groupValue += minerals[i] === "diamond" ? 100 : minerals[i] === "iron" ? 10 : 1;
    count++;

    if (count === 5) {
      groups.push(groupValue);
      groupValue = 0;
      count = 0;
    }
  }

  if (groupValue > 0 && groups.length < totalTools) {
    groups.push(groupValue);
  }

  groups.sort((a, b) => b - a);

  for (const value of groups) {
    const toolIndex = picks.findIndex((tool) => tool > 0);
    if (toolIndex === -1) break;

    picks[toolIndex]--;
    answer += Math.floor(value / 100) * efficiency[toolIndex][2];
    answer += Math.floor((value % 100) / 10) * efficiency[toolIndex][1];
    answer += (value % 10) * efficiency[toolIndex][0];
  }

  return answer;
}