프로그래머스 level2 : 광물 캐기 - Java

 

그리디로 풀수 있는 문제이다.

이문제를 가장 먼저 접근했을때 실수한 것이 무조건 맨 첨에 다이아 곡괭이부터 광물을 캐기 시작한다고 생각한 것이다. 

한 곡괭이 당 광물을 5개까지는 무조건 캐야하니

광물 리스트를 보고 가장 피로도가 높은 광물 구간은 가장 좋은 곡괭이로 캐야하는 것이다. 

그러기 위해선 가장 먼저 광물 리스트에서 5개씩 구간을 잘라서 해당 구간에서 곡괭이별 피로도 합산을 구해야한다.

 

1. 특정 구간의 곡괭이별 피로도 합산 클래스를 (내코드에선 TiredSumPerPick) 만들어야한다. 

2. 광물 리스트를 돌며 5개씩 피로도 합산을 구해서 피로도 합산 리스트를 만든다.

3. 피로도 합산 리스트에서 돌곡괭이로 캐는 경우 합산 값들끼리 비교하여 내림차순 정렬한다.

4. 곡괭이 리스트는 이미 가장 좋은 곡괭이부터 정렬되어있다. 그러므로 피로도 합산 리스트를 돌며 곡괭이 리스트 앞에서 부터 곡괭이 수를 -1 하면서 피로도를 결과에 합산 시킨다. 

 

import java.util.*;

class Solution {
    
    static class TiredSumPerPick {
        private int diamond;
        private int iron;
        private int stone;
        
        public TiredSumPerPick(int diamond, int iron, int stone){
            this.diamond = diamond;
            this.iron = iron;
            this.stone = stone;
        }
    }
    
    // 주어진 피로도 표 
    static int[][] scoreBoard;
    // 입력된 mineral을 Mineral 객체의 List
    static List<TiredSumPerPick> list;
    
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        
        scoreBoard = new int[][]{{1,1,1},{5,1,1},{25,5,1}};
        
        // 전체 곡괭이 수
        int totalPicks = Arrays.stream(picks).sum();
        list = new ArrayList<>();
        
        // 광물 5개 당 한번 곡괭이가 바뀜
        for(int i = 0; i < minerals.length; i+=5){
            if(totalPicks == 0) break;
            
            // 모든 곡괭이의 광물에 대한 피로도를 계산 - 5개까지
            int dia = 0, iron = 0, stone = 0;
            for(int j = i; j < i + 5; j++){
                if(j == minerals.length) break;
                
                String mineral = minerals[j];
                int m = mineral.equals("iron") ? 1 : mineral.equals("stone") ? 2 : 0;
                
                // 다이아로 캐는 경우
                dia += scoreBoard[0][m];
                // 철로 캐는 경우
                iron += scoreBoard[1][m];
                // 돌로 캐는 경우
                stone += scoreBoard[2][m];
            }
            list.add(new TiredSumPerPick(dia, iron, stone));
            totalPicks--;
        }
        
        // 돌곡괭이만 광물마다 피로도가 달라서 피로도가 젤 높은 광물부터 정렬하려면 돌곡괭이로 캐는 것 기준이 되어야함
        // 가장 피로도과 높은걸 앞에 놓았으니 아래의 picks를 앞에서부터 돌게 되면
        // 가장 피로도가 큰 광물을 가장 좋은 곡괭이로 캐게 됨.
        Collections.sort(list, ((o1, o2) -> (o2.stone - o1.stone)));
        
        // list를 다 돌면서 picks를 맨 앞부터 0을 만들며 돈다.
        // 곡괭이를 소진
        // picks의 곡괭이가 있으면 지금 광산에 대한 곡괭이의 피로도 합을 가져와서 answer에 합.
        for(TiredSumPerPick m : list){
            int dia = m.diamond;
            int iron = m.iron;
            int stone = m.stone;
            
            if(picks[0] > 0){
                answer += dia;
                picks[0]--;
                continue;
            }
            if(picks[1] > 0){
                answer += iron;
                picks[1]--;
                continue;
            }
            if(picks[2] > 0) { 
                answer += stone;
                picks[2]--;
                continue;
            }
        }
        
        return answer;
    }
}