[PS] 프로그래머스 광물캐기 ( Greedy ) with JAVA

프로그래머스

 

 

◎ 문제풀이

 

어려운 알고리즘이 필요한 문제는 아니었지만 적절한 풀이 발상이 쉽지 않은 문제였다. 

 

곡갱이는 종류에 상관없이 광물을 5개까지만 캘 수 있고 한번 캐기 시작하면 교체할 수 없다. 곡갱이의 종류에 따라 피로도가 달라지므로 최소 피로도를 구하려면, 가장 성능 좋은 곡갱이(다이아)로 가장 피로도가 높은 광물집합( 광물 5개 이하로 구성된 )을 캐야 한다. 

 

 

1) 곡갱이를 다이아-철-흙 순으로 곡갱이 큐에 넣는다. ( 성능순 )

2) 나열된 광물을 앞에서부터 5개씩 끊어 광물집합 객체를 생성하고 우선순위 큐에 넣는다. ( 피로도가 높은 순 )

3) 성능이 가장 좋은 곡갱이를 꺼내고 피로도가 가장 놓은 광물집합을 순서대로 꺼내어 피로도를 반복 계산한다. 

 

 

◎ 코드

import java.util.*;

class Solution {
    
    public static final String DIA = "diamond";
    public static final String IRON = "iron";
    public static final String STONE = "stone";
    
    
    public int solution(int[] picks, String[] minerals) {

        PriorityQueue<MineralSet> mineralQueue = new PriorityQueue<>((m1,m2)->m2.getTotalFatigue() - m1.getTotalFatigue());
        Queue<String> toolQueue = new LinkedList<>();
        int answer = 0;
        
        // 다이아->철->돌 순으로 곡갱이 큐에 삽입하기
        int toolCount = picks[0] + picks[1] + picks[2];
        for(int i=0;i<3;i++){
            int k = picks[i];
            String tool = ( i == 0 )? DIA : ( ( i == 1 )? IRON : STONE );
            while(k-- > 0){
                toolQueue.add(tool);
            }
        }
        
        // 앞에서부터 5개씩 분류하여 광물집합 클래스 생성하기
        int index = 0;
        while(toolCount-- > 0 && index < minerals.length){
            MineralSet mineralSet = new MineralSet();
            
            int limit = ( index+5 >= minerals.length)? minerals.length : index+5;
            for(int i=index;i<limit;i++){
                if(minerals[i].equals(DIA)) mineralSet.diaCount++;
                else if(minerals[i].equals(IRON)) mineralSet.ironCount++;
                else if(minerals[i].equals(STONE)) mineralSet.stoneCount++;
            }
            
            index = index+5;
            mineralQueue.add(mineralSet);// 우선순위 큐에 광물집합 클래스 넣기 
        }
        
        
        // 가장 성능 좋은 곡갱이로 가장 피로도가 높은 광물집합을 캐야 한다.
        while(!toolQueue.isEmpty()&&!mineralQueue.isEmpty()){
            
            String tool = toolQueue.poll(); // 곡갱이 꺼내기
            MineralSet mineralSet = mineralQueue.poll();// 광물 꺼내기
            
            answer += mineralSet.getFatigue(tool); // 피로도 계산
        }
        
        return answer;
    }
    
    public class MineralSet{
        
        private static final int DIA_FATIGUE = 25;
        private static final int IRON_FATIGUE = 5;
        private static final int STONE_FATIGUE = 1;
        
        public int diaCount;
        public int ironCount;
        public int stoneCount;
        
        public int getTotalFatigue(){
            return ( DIA_FATIGUE * diaCount + IRON_FATIGUE * ironCount + STONE_FATIGUE * stoneCount ); 
        }
        
        // 광물집합의 피로도는 돌곡갱이로 다이아,철,돌을 캘때 발생하는 피로도를 기준으로한다. 
        public int getFatigue(String tool){
            switch(tool){
                case DIA : return ( diaCount*1 + ironCount*1 + stoneCount*1 ); 
                case IRON : return ( diaCount*5 + ironCount*1 + stoneCount*1 ); 
                case STONE : return ( diaCount*25 + ironCount*5 + stoneCount*1 );
                default : return -1;
            }
        }
        
    }
}