프로그래머스_광물캐기_Day7

 

알고리즘 챌린지 7일차이다. 오늘로서 설 연휴 마지막날이기도 하다. 스스로 자제하고 덜 나간것도 있긴하지만 약속이 좀 적었어서 집에서 알고리즘을 풀 수 있었던것 같다 ㅋㅋ 

오늘은 프로그래머스 Level2로 분류된 광물 캐기 문제를 풀어보았다. 동적 계획법은 아니지만 그리디 알고리즘을 사용해서 풀이했다. 

문제에서 주어진 조건만 잘 분석하면 풀 수 있는 쉬운 문제였다. 

1. 세 개의 곡괭이 중에서 하나를 골라(=그리디 알고리즘) 최소 피로도를 구한다. 
2. 한 곡괭이로 최대 5개의 광물을 캘 수 있다, 선택한 곡괭이는 다 쓸때까지 바꿀 수 없다. (= 5개씩 그룹화)
3. 곡괭이를 다 쓰거나 광물을 다 캔 경우 종료한다. (= 반복의 탈출 조건)

코드의 주석을 달아놓았으니 이해가 어렵지 않을 것 같지만 핵심 로직을 간단히 설명하자면 아래와 같다. 

• dia, iron, stone의 각각의 피로도를 저장하는 Mineral 클래스를 만든다. 
• 광물의 순서가 바뀌지 않기 때문에 앞에서 부터 5개씩 끊어서 리스트에 저장한다. 
• 저장하는 내용은 해당 광물을 세 개의 곡굉이로 채굴했을때 소모되는 피로도를 Mineral 객체로 저장한다. 
• 모든 광물을 돌 곡괭이로 캐야하는 최악의 경우를 기준으로 내림차순 정렬한다. 
• 정렬 결과를 dia곡괭이부터 사용하여 피로도를 최소로 한다.

 

Java 소스

import java.util.*;
import java.util.stream.*;
class Solution {
    List<Mineral> mList; 
    int[][] pirodo;
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        pirodo = new int [][]{{1,1,1}, {5, 1 ,1}, {25, 5 ,1}};
        mList = new ArrayList<>();
        int totalPickCnt = Arrays.stream(picks).sum();
        
        //하나의 곡괭이로 채굴할 수 있는 광물이 최대 5개이고, 선택이후 변경이 불가능하므로 5개씩 그룹화
        for(int i=0; i<minerals.length; i+=5){
            //곡괭이가 부족하면 탈출
            if(totalPickCnt == 0 ) break; 
            
            int dia=0, iron =0, stone = 0;
            for(int j=i; j<i+5; j++){
                //광물의 개수가 5의 배수로 끊어지지 않으므로 광물을 다 캤다면 탈출
                if (j == minerals.length) break; 
                
                String mineral = minerals[j];
                int val = mineral.equals("iron") ? 1 : mineral.equals("stone") ? 2 : 0;
                
                //그룹에 포함된 광석들에 대해서 곡괭이 별로 피로도를 누적으로 구해 놓는다. 
                dia += pirodo[0][val];
                iron += pirodo[1][val];
                stone += pirodo[2][val];
                
            }
            mList.add(new Mineral(dia, iron, stone));
            //한 곡괭이로 5개의 광물 그룹에 대한 피로도를 구했으니 하나 제거하면서 반복 진행
            totalPickCnt--;
        }
        
        //모든 광물을 돌 곡괭이로 채굴한 경우(최악의 경우)를 기준으로 내림차순 정렬하자. 
        Collections.sort(mList, ((o1, o2) -> (o2.stone - o1.stone)));
        
        for(Mineral m : mList) {
            int dia = m.dia; 
            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;
    }
}

class Mineral{
    int dia; 
    int iron; 
    int stone; 
    
    public Mineral(int dia, int iron, int stone) {
        this.dia = dia;
        this.iron = iron;
        this.stone = stone;
    }
}