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

맨처음에는 DFS로 접근했는데 뭔가 잘못 짰는지
시간 초과가 났다
그래서 그리디로 접근했다

 

💡접근방식

1. 광물은 순서대로 캐야 하지만 곡괭이 순서는 상관이 없으므로 광물을 5개씩 묶음으로 잘라서 돌곡괭이 피로도 순으로 정렬해준다
2. 곡괭이로 캘 수 있는 만큼 광물 묶음을 잘라준다
   • 가지고 있는 곡괭이로 광물을 다 캐지 못할 수 있기 때문에 캘 수 없는 광물은 제거
3. 피로도 순으로 정렬된 광물 묶음을 다이아 > 철 > 돌 곡괭이 순으로 캐기

function solution(picks, minerals) {
	//곡괭이 수
    let pickCnt = picks.reduce((acc,cur)=>acc+cur, 0);
    //최종 피로도
    let result=0;
    const pick = ['diamond', 'iron', 'stone'];
    const table = {
    diamond: { diamond: 1, iron: 1, stone: 1 },
    iron: { diamond: 5, iron: 1, stone: 1 },
    stone: { diamond: 25, iron: 5, stone: 1 },
  };
    
    let sorted_minerals=[];
	
    // 5묶음으로 나눠서 각 곡괭이별 피로도 추가해줌
    for(let i=0;i<minerals.length;i+=5){
        const tmp_minerals=minerals.slice(i, i+5);
        let tmp_fatigue ={diamond:0, iron:0, stone:0};
        for(let i=0;i<5&&tmp_minerals.length>i;i++){
            tmp_fatigue['diamond']+=table['diamond'][tmp_minerals[i]];
            tmp_fatigue['iron']+=table['iron'][tmp_minerals[i]];
            tmp_fatigue['stone']+=table['stone'][tmp_minerals[i]];
   
        }
        sorted_minerals.push({minerals:tmp_minerals, fatigue:tmp_fatigue}) ;
    }
    
    //돌곡괭이 기준으로 정렬, 곡괭이 개수만큼 잘라줌
    sorted_minerals = sorted_minerals.slice(0,pickCnt).sort((a,b)=>a['fatigue']['stone']-b['fatigue']['stone']);
    
    //곡괭이를 다 쓰거나 광물을 다 캘 때까지 반복
    for(let i=0;i<3;i++){
    
        while(picks[i]){
            const item = sorted_minerals.pop();
            if(!item) break;
            result+=item['fatigue'][pick[i]];
            picks[i]--;
        }
    }
    
    
    
    
    

  return result;
}