프로그래머스 Lv2 - 광물 캐기

문제

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

프로그래머스

풀이 시간 : 60분

시도 횟수 : 1

복기

나는 BFS 풀이 방법이 생각나서 BFS 로 풀었다. 다만 DFS 풀이방법도 동시에 떠올리는게 유연한 사고측면에서 중요한거같다.

메모이제이션하며 최적화도 할 수 있지만, 문제에서 요구하진 않았다.

 

 

 

 

import java.util.*;
import java.util.stream.Collectors;
class Solution {
    
    int[][] costMap = {
        {1, 1, 1},
        {5, 1, 1},
        {25, 5, 1}
    };
    int grainCount = 0;
    
    public int solution(int[] picks, String[] minerals) {    
        int answer = 987654321;
        int N = minerals.length;
        Map<String, Integer> mineralIndexMap = new HashMap<>();
        mineralIndexMap.put("diamond", 0);
        mineralIndexMap.put("iron", 1);
        mineralIndexMap.put("stone", 2);
        int[] mineralList = Arrays.stream(minerals)
            .mapToInt(mineral -> mineralIndexMap.get(mineral))
            .toArray();
        
        grainCount = Arrays.stream(picks).sum();
        int[] initGrains = {0, 0, 0};
        Stage initStage = new Stage(0, initGrains, 0);
        
        
        Deque<Stage> queue = new LinkedList<>();
        queue.addLast(initStage);
        while (!queue.isEmpty()) {
            Stage stage = queue.pollFirst();
            if(stage.isFinish()){
                if(stage.score < answer) {
                    answer = stage.score;
                }
                continue;
            }
            for(int i = 0 ; i < 3 ; i++) {
                if (stage.grains[i] + 1 <= picks[i]) {
                    int cost = 0;
                    for(int j = 0 ; j < 5 && stage.stage + j < mineralList.length ; j++) {
                        cost += costMap[i][mineralList[stage.stage + j]];
                    }
                    
                    int[] grains = Arrays.copyOf(stage.grains, stage.grains.length);
                    grains[i] += 1;
                    queue.addLast(new Stage(stage.stage + 5, grains, stage.score + cost));
                }
            }
        }
        
        
        return answer;
    }
    
    class Stage {
        int stage;
        int[] grains;
        int score;
        
        Stage (int stage, int[] grains, int score) {
            this.stage = stage;
            this.grains = grains;
            this.score = score;
        }
        
        boolean isFinish(){
            return (grains[0] + grains[1] + grains[2]) == grainCount;
        }
    }
}

 

더 나은 풀이방법

이사람의 DFS 가 읽기 좋았다. 별도의 클래스를 만들지 않고 DFS로 상태를 트랙킹하며 풀어서 좋다.

 

class Solution {
    private static int min;
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;

        min = 987654321;
        int mineralsSize = minerals.length;
        dfs(picks, minerals, mineralsSize, 0, 0);

        answer = min;
        return answer;
    }

    public void dfs(int[] picks, String[] minerals, int mineralsSize, int idx, int fatigue){
        if(idx >= mineralsSize || (picks[0] == 0 && picks[1] == 0 && picks[2] == 0)){
            // System.out.println(fatigue);
            min = Math.min(min, fatigue);
            return;
        }

        if(picks[0] != 0){ // 다이아 곡괭이
            int tmp = mining(0, minerals, mineralsSize, idx, fatigue);
            int[] newPicks = {picks[0]-1, picks[1], picks[2]};
            dfs(newPicks, minerals, mineralsSize, idx+5, tmp);
        }
        if(picks[1] != 0){ // 철 곡괭이
            int tmp = mining(1, minerals, mineralsSize, idx, fatigue);
            int[] newPicks = {picks[0], picks[1]-1, picks[2]};
            dfs(newPicks, minerals, mineralsSize, idx+5, tmp);
        }
        if(picks[2] != 0){ // 돌 곡괭이
            int tmp = mining(2, minerals, mineralsSize, idx, fatigue);
            int[] newPicks = {picks[0], picks[1], picks[2]-1};
            dfs(newPicks, minerals, mineralsSize, idx+5, tmp);
        }
    }

    public int mining(int pick, String[] minerals, int mineralsSize, int idx, int fatigue){
        int tmp = 0;
        for(int i = 0; i<5; i++){ // 곡괭이는 5개 캠
            if(i+idx < mineralsSize){
                tmp += calFatigue(pick, minerals[i+idx]);
            }else{ // 모든 광물 캠                
                break;
            }
        }
        return fatigue+tmp;
    }

    public int calFatigue(int pick, String mineral){
        if(pick == 0){ // 다이아몬드 곡괭이
            return 1;
        }else if(pick == 1){ // 철 곡괭이
            if(mineral.equals("diamond")){
                return 5;
            }else if(mineral.equals("iron")){
                return 1;
            }else if(mineral.equals("stone")){
                return 1;
            }
        }else if(pick == 2){ // 돌 곡괭이
            if(mineral.equals("diamond")){
                return 25;
            }else if(mineral.equals("iron")){
                return 5;
            }else if(mineral.equals("stone")){
                return 1;
            }
        }
        return 0;
    }
}