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

 

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

프로그래머스

 

1. 첫번째 풀이

dfs의 요점은 2가지다

1. 어딜 반복할거며 반복할때 필요한 매개변수들

2. 반복을 끝내는 조건

 

반복

function dfs(남은도구들, 남은광물들, 피로도)

 

반복 끝내는 조건

 

남은 도구가 없거나 || 남은 광물이 없을때 최종피로도를 리턴한다.

도구가 없을 시 = [0, 0, 0] 이고 도구의 갯수는 >= 0이니까 reduce를 썼다

if (picks.reduce((acc, curr) => acc + curr, 0) === 0 || !minerals.length)

 

• 곡갱이 순서대로 주어진 광물들을 순서대로 채집한다.
• function dfs(남은곡갱이들, 남은광물들, 피로도)를 반복하며 곡갱이 종류의 모든 조합을 고려한다. -
• 반복을 끝내는 조건은 `if (picks.reduce((acc, curr) => acc + curr, 0) === 0 || !minerals.length)`
• 곡갱이를 사용한 뒤 남은 곡갱이는 picks[해당곡갱이 인덱스]--
• 곡갱이를 사용한 뒤 남은 광물은   
  • 남은 광물이 5개 이상인 경우 앞의 5개를 삭제하고 남은 광물이다   
  • 5개 미만인 경우 []이다
• 곡갱이를 사용한 뒤 누적된 피로도는   
  • 앞에서부터 최대5개의 피로도를 계산하여 누적한다.   
  • const rank = {diamond: 0,iron: 1,stone: 2}를 사용하여 곡갱이간의 diff를 구할 수 있다.   
  • 곡갱이의 랭킹 <= 광물의 랭킹인 경우 누적되는 피로도는 +1이다 
  • 그 외의 경우 `Math.pow(5, 곡갱이 랭킹-광물랭킹)`로 피로도를 구한다.

 

피로도 계산하기

광물별 랭킹을 빨리 찾기 위해 rank obj을 만든다.

도구랭킹 <= 광물랭킹 이면 피로도+1

도구랭킹 > 광물랭킹이면 피로도 += Math.pow(5, 도구랭킹-광물랭킹)

// 피로도계산
for (let i = 0; i < (minerals.length >= 5 ? 5 : minerals.length); i++) {
    const currMineralRank = rank[minerals[i]]; // 현재 캘 광물의 랭킹
    if (currPickRank <= currMineralRank) {
        fatigue += 1;
    } else {
        fatigue += Math.pow(5, currPickRank-currMineralRank);
    }
}

 

 

전체코드

 

function solution(picks, minerals) {
  let answer = Infinity;
  const rank = {
    diamond: 0,
    iron: 1,
    stone: 2,
  };

  function dfs(picks, minerals, fatigue) {
    // 도구가 없거나 광물이 없을때 return
    if (picks.reduce((acc, curr) => acc + curr, 0) === 0 || !minerals.length) {
      answer = Math.min(answer, fatigue);
      return;
    }

    // 도구별 피로도 계산
    for (let i = 0; i < picks.length; i++) {
      let newFatigue = fatigue;
      const currPickCount = picks[i];
      const currPickRank = i;
      // 도구가 없을땐 다음 도구로 스킵
      if (!currPickCount) {
        continue;
      }
      // 도구가 있다
      const newPicks = [...picks];
      newPicks[i] -= 1; // 도구 삭제
      const newMinerals = minerals.length <= 5 ? [] : [...minerals].splice(5); // 캐고 남은 광물

      // 피로도계산
      for (let i = 0; i < (minerals.length >= 5 ? 5 : minerals.length); i++) {
        const currMineralRank = rank[minerals[i]]; // 현재 캘 광물의 랭킹
        if (currPickRank <= currMineralRank) {
          newFatigue += 1;
        } else {
          newFatigue += Math.pow(5, currPickRank - currMineralRank);
        }
      }
      dfs(newPicks, newMinerals, newFatigue);
    }
  }
  dfs(picks, minerals, 0);
  return answer;
}

 

 

느낀점

 

처음에는 복잡한 경우를 다 생각하다보니 반복하는 부분을 어떻게 풀어 써야할지 몰랐는데

그림을 그리고 한가지 경우에만 집중해서 dfs 매개변수와 탈출조건을 생각하다보니 풀렸다.

 

생각을 너무 많이 하지말고, 일단 푸는게 중요하니 매개변수나 대략적인 방법이 생기면 일단 그걸로 고정시키고 쭉 로직을 적어보기

• 가지치기로 다양한 경우가 존재할 때에는 dfs를 사용해 완전탐색을 생각해 볼 수 있다.
• object를 사용하여 두 광물의 diff계산을 쉽게 할 수 있다.