Level 2️⃣ - 광물 캐기

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

프로그래머스

문제 접근

순열을 활용해서 문제를 해결하려고 하니 시간 초과가 나왔다.

1. picks 배열을 이용해서 사용할 곡괭이 경우의 수를 순열로 구한다. 이때 이미 구한 경우의 수라면 생략한다. 
2. 곡괭이의 경우의 수마다 광물을 캔다.
3. 최소 피로도를 구한다.

 

function solution(picks, minerals) {
    const table = [[1,1,1],[5,1,1],[25,5,1]];
    let formatted = [];
    let ret = Number.MAX_SAFE_INTEGER;
    
    picks.forEach((elem, idx)=>{
        if(idx === 0){
            while(elem){
                formatted.push('d');
                elem -= 1;
            }
        }
        else if(idx === 1){
            while(elem){
                formatted.push('i');
                elem -= 1;
            }
        }
        else {
            while(elem){
                formatted.push('s');
                elem -= 1;
            }
        }
    });

    const check = Array.from({length: formatted.length}).fill(0);
    const tmp = [];
    const memo = new Map();
    function permutation(level){
        if(level === formatted.length){
            let str = tmp.join("");
            if(memo.has(str)) return;
            memo.set(str, 1);
            let copy = [...minerals];
            let f = 0;
            let i = 0;
            for(const pick of str){
                if(!copy.length) break;
                let cnt = 5;
                if(pick === 'd'){
                    while(cnt && i < minerals.length){
                        let item = copy[i++];
                        if(item === 'diamond') f += table[0][0];
                        else if(item === 'iron') f += table[0][1];
                        else f += table[0][2];
                        cnt -= 1;
                    }
                }
                if(pick === 'i'){
                    while(cnt && i < minerals.length){
                        let item = copy[i++];
                        if(item === 'diamond') f += table[1][0];
                        else if(item === 'iron') f += table[1][1];
                        else f += table[1][2];
                        cnt -= 1;
                    }
                }
                if(pick === 's'){
                    while(cnt && i < minerals.length){
                        let item = copy[i++];
                        if(item === 'diamond') f += table[2][0];
                        else if(item === 'iron') f += table[2][1];
                        else f += table[2][2];
                        cnt -= 1;
                    }
                }
            }
            ret = Math.min(ret, f);
        }
        else {
            for(let i = 0; i < formatted.length; i++){
                if(check[i] === 1) continue;
                check[i] = 1;
                tmp.push(formatted[i]);
                permutation(level + 1);
                check[i] = 0;
                tmp.pop();
            }
        }
    }
    permutation(0);
    
    return ret;
}

 

문제 접근을 다시 할 필요가 있다.

최소 피로도를 구하는 방법으로 그리디를 생각해보기로 했다.

만약 다이아몬드 곡괭이 1개, 철 곡괭이 1개가 있고 철 5개, 다이아몬드 5개를 캐려고 한다.

순서대로 다이아몬드 곡괭이부터 철 5개를 캐고, 그 다음에 철 곡괭이로 다이아몬드 5개를 캐면 피로도가 30이다.

하지만 철 곡괭이부터 철 5개를 캐고, 그 다음에 다이아몬드 곡괭이로 다이아몬드를 캐면 피로도는 10이 된다.

즉, 하나의 곡괭이로 5개의 광물을 캘 수 있기 때문에 5개씩 묶어주고, 해당 묶음에서 다이아몬드, 철, 돌의 갯수를 카운팅한다.

그리고 묶음의 배열을 다이아몬드 > 철 > 돌의 갯수 순으로 내림차순 정렬을 한다. 이 부분이 그리디의 핵심이다.

 

참고 블로그

https://cocococo.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4JavaScript-Lv2-%EA%B4%91%EB%AC%BC-%EC%BA%90%EA%B8%B0#google_vignette

[프로그래머스/JavaScript] Lv.2 광물 캐기

function solution(picks, minerals) {
    let answer = 0;
    const sortArr = [];
    const tired = [
        [1, 1, 1],
        [5, 1, 1],
        [25, 5, 1]
    ];
    const len = Math.ceil(minerals.length / 5); // 광물을 5개씩 자른 횟수
    const maxLen = picks[0] + picks[1] + picks[2]; // 곡괭이의 갯수
    
    for(let i = 0; i < len; i++){
        // 곡괭이의 갯수보다 크면 반복문을 빠져나온다.
        if(i >= maxLen) break;
        const arr = [0, 0, 0]; // 다이아, 철, 돌 갯수
        minerals.splice(0, 5).forEach(item => {
            switch(item){
                case 'diamond' :
                    arr[0]++;
                    break;
                case 'iron' :
                    arr[1]++;
                    break;
                default :
                    arr[2]++;
                    break;
            }
        });
        sortArr.push(arr);
    }
    // 다이아 > 철 > 돌 우선순위로 내림차순 정렬한다. (그리디의 핵심)
    sortArr.sort((a, b)=>{
        if(a[0] === b[0]){
            if(a[1] === b[1]) {
                return b[2] - a[2];
            }
            else {
                return b[1] - a[1];
            }
        }
        else {
            return b[0] - a[0];
        }
    });
    // 피로도를 계산한다.
    sortArr.forEach((item)=>{
        const [d, i, s] = item;
        let idx = 0;
        // 피로도를 계산하기 위해 다이아 > 철 > 돌 순서로 곡괭이가 있는지 확인하고 idx 값을 결정한다.
        if(picks[0]) idx = 0;
        else if(picks[1]) idx = 1;
        else if(picks[2]) idx = 2;

        if(picks[idx]){
            answer += tired[idx][0] * d;
            answer += tired[idx][1] * i;
            answer += tired[idx][2] * s;
            // 사용한 곡괭이를 감소시킨다.
            picks[idx]--;
        }
    });
    
    return answer;
}