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

문제

광물 캐기

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

 

 

예시 코드

function solution(picks, minerals) {
  const DIAMOND = "diamond";
  const IRON = "iron";
  const STONE = "stone";
  const MAX_MINERALS_PER_PICK = 5;

  const fatigueCost = {
    diamond: [1, 1, 1],
    iron: [5, 1, 1],
    stone: [25, 5, 1],
  };

  const MINERAL_LIST = [DIAMOND, IRON, STONE];

  const REQUIRED_PICKS = Math.ceil(minerals.length / MAX_MINERALS_PER_PICK);
  const TOTAL_PICKS = picks.reduce((acc, cur) => acc + cur, 0);
  const PICKS_TO_BE_USED = Math.min(REQUIRED_PICKS, TOTAL_PICKS);
  let [diamondPicks, ironPicks, stonePicks] = [...picks];
  const pq = new PriorityQueue();
  let minFatigueSum = 0;

  for (let i = 0; i < PICKS_TO_BE_USED; i++) {
    const startIdx = i * MAX_MINERALS_PER_PICK;
    const endIdx = startIdx + MAX_MINERALS_PER_PICK;
    const mineralGroup = minerals.slice(startIdx, endIdx);

    const fatigueSumWithDimondPick = mineralGroup.length;
    let fatigueSumWithIronPick = 0;
    let fatigueSumWithStonePick = 0;

    for (const mineral of mineralGroup) {
      fatigueSumWithIronPick +=
        fatigueCost[IRON][MINERAL_LIST.indexOf(mineral)];
      fatigueSumWithStonePick +=
        fatigueCost[STONE][MINERAL_LIST.indexOf(mineral)];
    }

    pq.enqueue(
      [
        fatigueSumWithDimondPick,
        fatigueSumWithIronPick,
        fatigueSumWithStonePick,
      ],
      fatigueSumWithStonePick
    );
  }

  for (let i = 0; i < PICKS_TO_BE_USED; i++) {
    const [
      fatigueSumWithDimondPick,
      fatigueSumWithIronPick,
      fatigueSumWithStonePick,
    ] = pq.dequeue().value;

    let fatigueSum = 0;
    if (diamondPicks) {
      fatigueSum = fatigueSumWithDimondPick;
      diamondPicks--;
    } else if (ironPicks) {
      fatigueSum = fatigueSumWithIronPick;
      ironPicks--;
    } else {
      fatigueSum = fatigueSumWithStonePick;
      stonePicks--;
    }

    minFatigueSum += fatigueSum;
  }

  return minFatigueSum;
}

 

풀이

작업을 끝내기까지 필요한 최소한의 피로도를 구하는 문제입니다.

 

작업은 아래 두 가지 조건 중 하나를 만족할 경우 끝납니다.

• 광산에 있는 모든 광물을 캤을 경우
• 더이상 사용할 곡괭이가 남지 않은 경우

 

광물을 캐는 규칙입니다.

• 곡괭이 하나 당 광물을 5개까지 캘 수 있다.
• 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용해야 한다.
• 광물은 주어진 순서대로만 캘 수 있다.

 

광물은 앞에서부터 5개씩 묶여 하나의 그룹을 이루며, 곡괭이 하나에 할당됩니다. 마지막 그룹은 5개보다 적을 수 있습니다. 

작업에 사용할 곡괭이 수는 모든 광물을 캘 때 필요한 곡괭이 수와 가지고 있는 곡괭이 수 중 더 작은 값입니다. 이 값은 작업할 그룹수와 같습니다.

 const PICKS_TO_BE_USED = Math.min(REQUIRED_PICKS, TOTAL_PICKS);

 

곡괭이 종류에 따라 각 광물을 캘 때 소모되는 피로도가 다르기 때문에, 곡괭이를 사용하는 순서를 적절하게 배치해야 하는데요.

피로도를 최소한으로 사용하려면, 피로도가 가장 많이 필요한 그룹에 가장 좋은 곡괭이를 사용해야 합니다.

 

피로도가 가장 많이 필요한 그룹을 찾기 위해 우선순위 큐를 사용했습니다.

우선순위 큐의 원소에는 value와 priority가 필요한데요.

value에는 곡괭이 종류 별(다이아몬드, 철, 돌)로 해당 그룹을 작업하는데 필요한 피로도를, priority에는 돌 곡괭이를 사용했을 때 소모되는 피로도를 넣습니다. 돌 곡괭이로 작업할 때 피로도가 가장 크기 때문입니다.

  for (let i = 0; i < PICKS_TO_BE_USED; i++) {
    const startIdx = i * MAX_MINERALS_PER_PICK;
    const endIdx = startIdx + MAX_MINERALS_PER_PICK;
    const mineralGroup = minerals.slice(startIdx, endIdx);

    const fatigueSumWithDimondPick = mineralGroup.length;
    let fatigueSumWithIronPick = 0;
    let fatigueSumWithStonePick = 0;

    for (const mineral of mineralGroup) {
      fatigueSumWithIronPick +=
        fatigueCost[IRON][MINERAL_LIST.indexOf(mineral)];
      fatigueSumWithStonePick +=
        fatigueCost[STONE][MINERAL_LIST.indexOf(mineral)];
    }

    pq.enqueue(
      [
        fatigueSumWithDimondPick,
        fatigueSumWithIronPick,
        fatigueSumWithStonePick,
      ],
      fatigueSumWithStonePick
    );
  }

 

마지막으로 우선순위 큐에서 순서대로 원소를 빼고, 실제 소모되는 피로도를 구해 합산합니다.

피로도를 최소화하기 위해, 다이아몬드, 철, 돌 곡괭이 순으로 사용합니다.

for (let i = 0; i < PICKS_TO_BE_USED; i++) {
    const [
      fatigueSumWithDimondPick,
      fatigueSumWithIronPick,
      fatigueSumWithStonePick,
    ] = pq.dequeue().value;

    let fatigueSum = 0;
    if (diamondPicks) {
      fatigueSum = fatigueSumWithDimondPick;
      diamondPicks--;
    } else if (ironPicks) {
      fatigueSum = fatigueSumWithIronPick;
      ironPicks--;
    } else {
      fatigueSum = fatigueSumWithStonePick;
      stonePicks--;
    }

    minFatigueSum += fatigueSum;
  }