프로그래머스 lv2 광물캐기- greedy

 

 

깽~깽~

 

문제를 읽어보면

곡괭이의 종류에 따라 광물을 캐는 효율이 다르다.

1개의 곡괭이를 들면 5개의 광물을 캐게 된다.

모든 광물을 캐거나 곡괭이가 없을때까지 진행 후, 가장 효율적으로 캐는 방법을 구하는 문제다

 

바로 그리디가 떠올랐고, 한번 곡괭이를 쓸때 5개의 광물을 캐기 때문에 

5개의 광물씩 묶어 그룹화 하고 정렬을 통해 가장 피로도가 높은 집단에서부터 가장 좋은 곡괭이를 소모시키게 작성했다.

그룹에는 총 광물의 가치가 몇인지, 다이아, 철, 돌의 개수 를 포함시켰다.

 

groups.sort(Comparator.comparingInt(Group::getValue).reversed());

 

 

다만 예외사항이 존재했다.

꺄오~

 

만약 광물이 6개고 ["stone", "stone", "stone", "stone", "stone", "diamond"] 로 주어졌다고 가정하자.

곡괭이는 [0,0,1] 로 주어진 경우 무조건 피로도가 높은 순서로 정렬하기 때문에 diamond를 캐게된다.

그냥 돌만캐면 5였지만 다이아를 캐게되므로 25가 되게 된다.

따라서

 if (minerals.length > maxMinerals) {
            minerals = java.util.Arrays.copyOf(minerals, maxMinerals);
        }

 

을 통해 정렬하기 전, 곡괭이가 캘수있는 만큼의 광물 개수로만 지정해주고 정렬하면 된다.

 

import java.io.*;
import java.util.*;    
class Solution {
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        int totalPicks = picks[0] + picks[1] + picks[2];
        int maxMinerals = totalPicks * 5;
        
        // 광물을 최대 채굴 가능 수로 제한
        if (minerals.length > maxMinerals) {
            minerals = java.util.Arrays.copyOf(minerals, maxMinerals);
        }
        
        List<Group> groups = checkValue(minerals);
        
        groups.sort(Comparator.comparingInt(Group::getValue).reversed());
 
        for (Group group : groups) {
            if (picks[0] > 0) { 
                answer += group.getDiamondCount() + group.getIronCount() + group.getStoneCount();
                picks[0]--;
            } else if (picks[1] > 0) { 
                answer += group.getDiamondCount() * 5 + group.getIronCount() + group.getStoneCount();
                picks[1]--;
            } else if (picks[2] > 0) {
                answer += group.getDiamondCount() * 25 + group.getIronCount() * 5 + group.getStoneCount();
                picks[2]--;
            } else {
                break; // 모든 곡괭이를 다 사용한 경우 종료
            }
        }
        return answer;
    }
 
    public List<Group> checkValue(String[] minerals) {
        int mineralsGroups = (minerals.length + 4) / 5;  // 5개씩 나눌 그룹 수 계산
        List<Group> groupsValue = new ArrayList<>();
 
        for (int i = 0; i < minerals.length; i += 5) {
            int groupValue = 0;
            int diamondCount = 0;
            int ironCount = 0;
            int stoneCount = 0;
            for (int j = 0; j < 5 && i + j < minerals.length; j++) {
                String type = minerals[i + j];
                switch (type) {
                    case "diamond" -> {
                        groupValue += 25;
                        diamondCount++;
                    }
                    case "iron" -> {
                        groupValue += 5;
                        ironCount++;
                    }
                    case "stone" -> {
                        groupValue += 1;
                        stoneCount++;
                    }
                }
            }
            groupsValue.add(new Group(groupValue, diamondCount, ironCount, stoneCount));
        }
        return groupsValue;
    }
 
    class Group {
        private final int value;
        private final int diamondCount;
        private final int ironCount;
        private final int stoneCount;
 
        public Group(int value, int diamondCount, int ironCount, int stoneCount) {
            this.value = value;
            this.diamondCount = diamondCount;
            this.ironCount = ironCount;
            this.stoneCount = stoneCount;
        }
 
        public int getValue() {
            return value;
        }
 
        public int getDiamondCount() {
            return diamondCount;
        }
 
        public int getIronCount() {
            return ironCount;
        }
 
        public int getStoneCount() {
            return stoneCount;
        }
    }
}