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

링크

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

프로그래머스

 

---

풀이

그리디를 통해 푸는 문제였다.

 

광물은 캐기 시작하면 바꿀 수 없다. 광물은 연속으로 5개씩 캔다. 그리고 테스트 케이스의 최대 개수가 적다. 의 힌트를 생각하면 해당 유형임을 좀 더 파악하기 쉬울 것 같다.

 

각 광물들을 5개의 그룹으로 하나씩 묶는다. 그리고 광물들의 weight를 준다.

weight는 다이아몬드라고 했을 때 31, 철이라고 했을 때 6 돌이라고 했을 때 각각 1로 주었다고 생각해보자.

이 광물들을 내림차순으로 정렬하고 가장 무거운 weight의 광물들부터 다이아몬드 곡괭이부터 처리하면 된다.

 

또한, 처리해야할 곡괭이보다 광물의 갯수가 많다면 처음 광물은 아예 캐지 않는 경우가 있을 수 있다.

이런 경우에는 처리하지 않을 만한 크기만 후보로 잡은 후에 그룹으로 묶어주어야 한다.

 

import java.util.*;

class Solution {
    static Map<String, Integer> picksMap = new HashMap<>();
    
    public int solution(int[] picks, String[] minerals) {
        picksMap.put("diamond", 31);
        picksMap.put("iron", 6);
        picksMap.put("stone", 1);
        int diamondPick = picks[0];
        int ironPick = picks[1];
        int stonePick = picks[2];
        
        int possibleMiningMineralsSize = Math.min((picks[0] * 5 + picks[1] * 5 + picks[2] * 5), minerals.length);
        
        double splitLen = Math.ceil((double) possibleMiningMineralsSize / 5);
        List<PickWeightGroup> pickWeightGroups = new ArrayList<>();
        for (int i=0; i<splitLen; i++) {
            pickWeightGroups.add(new PickWeightGroup());
        }
        
        for (int i=0; i<possibleMiningMineralsSize; i++) {
            String mineral = minerals[i];
            int currentGroupIndex = i / 5;
            PickWeightGroup pickWeightGroup = pickWeightGroups.get(currentGroupIndex);
            pickWeightGroup.addWeight(mineral);
        }
        
        Collections.sort(pickWeightGroups, (p1, p2) -> Integer.compare(p2.totalWeight, p1.totalWeight));
        
        int fatiguePoint = 0;
        for (int i=0; i<pickWeightGroups.size(); i++) {
            PickWeightGroup cWeightGroup = pickWeightGroups.get(i);
            List<String> mineralsInWeightGroup = cWeightGroup.minerals;
            
            if (diamondPick > 0) {
                for (int j=0;j<mineralsInWeightGroup.size();j++) {
                    String currentMineral = mineralsInWeightGroup.get(j);
                    // 피로도 계산
                    fatiguePoint++;
                }
                diamondPick--;
                continue;
            }
            
            if (ironPick > 0) {
                for (int j=0;j<mineralsInWeightGroup.size();j++) {
                    String currentMineral = mineralsInWeightGroup.get(j);
                    // 피로도 계산
                    if (currentMineral.equals("diamond")) {
                        fatiguePoint += 5;
                    } else {
                        fatiguePoint++;
                    }
                }
                ironPick--;
                continue;
            }
            
            if (stonePick > 0) {
                for (int j=0;j<mineralsInWeightGroup.size();j++) {
                    String currentMineral = mineralsInWeightGroup.get(j);
                    // 피로도 계산
                    if (currentMineral.equals("diamond")) {
                        fatiguePoint += 25;
                    } else if (currentMineral.equals("iron")) {
                        fatiguePoint += 5;
                    } else {
                        fatiguePoint++;
                    }
                }
                stonePick--;
                continue;
            }
            // 곡괭이 소모 완료
            if (diamondPick == 0 && ironPick == 0 && stonePick == 0) {
                break;
            }
        }
        
        return fatiguePoint;
    }

    class PickWeightGroup {
        int totalWeight;
        List<String> minerals;

        PickWeightGroup() {
            this.totalWeight = 0;
            this.minerals = new ArrayList<>();
        }

        public void addWeight(String mineral) {
            int weight = picksMap.get(mineral);
            minerals.add(mineral);
            totalWeight += weight;
        }

    }
}