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

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

프로그래머스

코딩 테스트 준비를 위해 웜업으로 풀이한 문제지만 유형이 익숙하지 않다 보니 GPT의 도움도 받고 시간이 걸렸음

 

처음 풀이과정에서는 제한사항이 그렇게 크지 않아 전체 탐색을 해도 되겠다 싶어서 dfs를 통해 경우의 수를 모두 구하는 방식을 사용했음

 

하지만 테스트 케이스 중 통과되는 케이스가 있었지만 조건문을 잘못 사용했는지 절반정도가 실패했음

 

GPT에게 질문한 결과 문제의 조건이 한번 사용하면 5개의 광물까지 사용해야 하기 때문에 5개를 기준으로 블록을 만듦

 

블록을 반복문을 통해 순회하면서 돌 곡괭이로 캤을 때의 피로도를 계산하여 내림차순으로 정렬하여 블록의 우선순위를 구할 수 있음

 

위와 같은 방법으로 구현한 후 테스트했을 때 단 하나의 케이스에서 실패가 발생했는데 그 케이스는 곡괭이 수보다 블록의 수가 많고 뒤 블록이 우선수위를 가질 때 광물의 순서가 지켜지지 않기 때문에 실패한 케이스임

실패 예시 케이스
[0, 1, 0]
["diamond", "diamond", "iron", "iron", "iron", "iron", "iron", "diamond", "diamond", "diamond", "diamond"]
13

 

따라서 블록의 우선순위를 정할 때 블록 배열의 길이와 곡괭이의 총개수를 비교해 더 작은 것을 기준으로 블록 배열을 slice 하여 우선순위를 구함

 

그리디 알고리즘을 사용하는 문제를 많이 접하지 못해서 바로 풀이가 생각나지 않았던 것 같음 계속해서 경험해 가는 것이 중요해 보임

 

추가로 dfs로 풀이하려 했을 때 왜 풀리지 않았는지 추후 다시 풀이하고 싶음

function solution(picks, minerals) {
    var answer = 0;
    
    const blocks = [];
    
    for(let i = 0; i < Math.ceil(minerals.length / 5); i++){
        blocks.push(minerals.slice(i * 5, (i + 1) * 5).map(it => {
            if(it == 'diamond') return 0;
            else if(it == 'iron') return 1;
            else if(it == 'stone') return 2;
        }));
    }
    
    const totalPicks = picks[0] + picks[1] + picks[2];
    const K = Math.min(blocks.length, totalPicks);
    
    let hardness = blocks.slice(0, K).map((block, idx) => {
        let cost = 0;
        block.forEach((it) => {
            cost += Math.pow(5, 2 - it);
        })
        return [cost, idx];
    }).sort((a, b) => (b[0] - a[0]));
    
    for(let i = 0; i < hardness.length; i++){
        const index = hardness[i][1];
        
        for(let j = 0; j < picks.length; j++){
            if(picks[j] < 1) continue;
            
            blocks[index].forEach(block => {
                if(j <= block) answer += 1;
                else answer += Math.pow(5, j - block);
            });
            
            picks[j] -= 1;
            break;
        }
    }

    return answer;
}

 

---

25. 05. 24

완전탐색으로 다시 풀어보았을 때 이전에 풀이할 때와 다른 점은 blocks를 먼저 정의해서 쉽게 풀 수 있었던 거 같음

 

그리디 문제를 완전탐색으로 풀었을 때 경우의 수를 유추할 수 있게 연습이 된 거 같음, 해당 문제는 blocks 최대길이가 10, 각 곡괭이가 모두 있을 때 한 스텝을 진행할 때마다 3가지 경우의 수가 늘어나므로 3의 10승이 됨

 

3의 10승은 59049로 충분히 계산할 수 있는 범위임

 

종료 조건은 step이 blocks의 길이와 같아지거나 모든 곡괭이가 0이 되었을 때로 잡음

 

피로도를 계산하는 부분은 공통화하지 않고 직관적으로 풀이함

function solution(picks, minerals) {
    var answer = Infinity;
    
    const blocks = [];
    
    for(let i = 0; i < Math.ceil(minerals.length / 5); i++){
        blocks.push(minerals.slice(i * 5, (i + 1) * 5).map(it => {
            if(it == 'diamond') return 0;
            else if(it == 'iron') return 1;
            else if(it == 'stone') return 2;
        }));
    }
    
    const dfs = (currPicks, step, cost) => {
        // 종료 조건
        if(step == blocks.length || currPicks.every(it => it === 0)){
            answer = Math.min(answer, cost);
            return;
        }
        
        const [dia, iron, stone] = currPicks;
        const currBlock = blocks[step];
        
        if(dia){
            const sum = currBlock.reduce((acc, curr) => {
                return acc + 1;
            }, 0)
            
            dfs([dia - 1, iron, stone], step + 1, cost + sum);
        }
        
        if(iron){
            const sum = currBlock.reduce((acc, curr) => {
                if(curr == 0){
                    return acc + 5;
                } else {
                    return acc + 1;
                }
            }, 0)
            
            dfs([dia, iron - 1, stone], step + 1, cost + sum);
        }
        
        if(stone){
            const sum = currBlock.reduce((acc, curr) => {
                if(curr == 0){
                    return acc + 25;
                } else if(curr == 1) {
                    return acc + 5;
                } else{
                    return acc + 1;
                }
            }, 0)
            
            dfs([dia, iron, stone - 1], step + 1, cost + sum);
        }
    }
    
    dfs(picks.slice(), 0, 0);
    return answer;
}