[프로그래머스] 광물 캐기 풀이 java

1. 문제 설명

문제 링크

2. 접근 방식

KEY WORD: GREEDY Algorithm

광물을 캐는 비용을 최소화 하기 위해서는, 돌 곡괭이로 캤을 때, 비용이 제일 많이 드는 구간이 앞에 오도록, 광물 리스트를 정렬하고, 구간들을 순회하며, 그때 그때 최선의 곡괭이로 일처리를 해야한다.
그 의미에서 Greedy Algorithm을 써야 하는 것이다.

광물의 크기가 50밖에 안됨으로 시간복잡도 관련해서 걱정할 것은 없을 것 같다. 그렇다면 해야할 일은,

1. 광물 List를 5개씩 자른다. 그것이 일의 단위이기 때문이다.
   (근데 광물이 5의 배수로 안 맞아 떨어질 수 있다. 그러면 맨 마지막은 3개나 4개가 하나의 묶음이 될 수도 있음으로 이를 주의해서 Loop를 짠다.)
2. 나눠진 광물 묶음을 돌 곡괭이로 작업했을 때 피로도가 가장 많이 드는 순으로 정렬한다.
3. 이제 가지고 있는 곡괭이 중에서 최선의 곡괭이를 이용하여 첫 구간부터 순서대로 작업하고 피로도를 총합 한다.
   (※ 주의점: Loop문으로 해당 부분을 구현할 때, 곡괭이를 먼저 다 써버리거나, 작업할 것이 먼저 끝나버리거나, 하는 경우에 대한 제어 장치가 필요하다.)

3. 코드 분석

import java.io.*;
import java.util.*;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        // 1. 광물을 5개씩 잘라서 (맨 마지막은 낱개 끼리) 각 곡괭이로 했을 때 cost가 얼마나 드는지 계산 
        // 2. 돌 곡괭이로 작업했을 때 드는 비용을 기준으로 정렬
        // (해당 기준이 각 단위별 코스트 차이가 극명히 들어남. + 돌 곡괭이로 cost가 많이 든다 
        //                                                     == 다른 곡괭이들로도 cost가 많이 든다.)
        // 3. 곡괭이를 다 쓰거나 아니면, 돌을 전부 처리하거나 할 때까지 작업 반복 
        // (해당 단위에서 피로도가 가장 적게 드는 곡괭이를 선정하여 쓴다.)

        List<Mineral> stress = new ArrayList<>(); 
        // 모든 곡괭이 수를 더한다.
        int pick_cnt = Arrays.stream(picks).sum();
        // 최대 작업량을 구한다. 쓸 수 있는 곡괭이 수, 광물량 중 적은 쪽이 최대 작업량이다.
        int work_cnt = Math.min(pick_cnt*5, minerals.length);
        //돌 곡괭이로 했을 때, 구간별 최대 작업량을 구해 놓을 것이다. 
        for(int i =0; i<work_cnt; i+=5){   
            int d_cost = 0;
            int i_cost = 0;
            int s_cost = 0;

            for(int j = 0; j<5; j++){
                int next = i+j;
                // 중요! -> 최대 작업량을 넘어갈 시 더 이상 계산하지 않는다! 
                // 맨 마지막 묶음이 1~4개의 낱개로 되어있을 경우, 해당 break 문을 통해 적절히 탈출할 수 있다!
                if(next == work_cnt) break;

                switch(minerals[next]) {
                    case "diamond": {
                        d_cost+=1;
                        i_cost+=5;
                        s_cost+=25;
                        break;
                    }
                    case "iron": {
                        d_cost+=1;  
                        i_cost+=1;
                        s_cost+=5;
                        break;
                    }
                    case "stone": {
                        d_cost+=1;
                        i_cost+=1;
                        s_cost+=1;
                        break;
                    }
                }  
            }
            // 각 구간 별 다이아, 철, 돌 곡괭이로 작업했을 때,
            // 피로도를 계산해서, stress(피로도) 리스트에 저장한다. 
            stress.add(new Mineral(d_cost, i_cost, s_cost));
        }
        // 내림차순(비용 많이 드는 묶음 순으로 정렬)
        Collections.sort(stress, (o1,o2) -> o2.s_cost - o1.s_cost);
        int min_cost = 0;
        for(int i =0; i< stress.size(); i++){
            // 곡괭이 다 쓰면 탈출
            if(picks[0] == 0 && picks[1] == 0 && picks[2] == 0) break;
            // 다이아 -> 철 -> 돌 곡괭이 순으로 사용
            if(picks[0] > 0) {picks[0]--; min_cost += stress.get(i).d_cost;}
            else if(picks[1] > 0) {picks[1]--; min_cost += stress.get(i).i_cost;}
            else if(picks[2] > 0) {picks[2]--; min_cost += stress.get(i).s_cost;}
        }
        // 피로도의 총합 반환
        return min_cost;
    }
}

// 구간 별, 각 곡괭이로 작업했을 때의 피로도를 저장한다.
class Mineral {
    int d_cost;
    int i_cost;
    int s_cost;

    public Mineral(int d, int i, int s){
        this.d_cost = d;
        this.i_cost = i;
        this.s_cost = s;
    }
}

4. 성장하기

해당 문제는 최대 비용으로 정렬 후, Greedy 사용 인 것은 빨리 catch 했지만,
구간을 묶었을 때 5개가 꽉 안 차는 묶음에 대한 처리, 곡괭이가 먼저 동이 날 때, 혹은 광물을 먼저 다 캐버렸을 때에 대한 처리가 미흡해서 문제를 풀지 못했다.

프로그래머스는 배열 index 초과 시, 어디서 초과했다고 안 보여줘서 더 찾기가 힘들었다. 그래서 인텔리제이에다가 복붙해서 문제를 찾았다.
내가 너무 어렵게 구현한 것이 화근인 것 같다.

 int cost =  0;
            int share = minerals.length/5;
            int remainder = minerals.length%5;
            int cost_length = remainder==0? share : share+1;

            Cost [] allCost = new Cost [cost_length];

            for(int i = 0; i < cost_length; i++) {
                int d_cost = 0;
                int i_cost = 0;
                int s_cost = 0;
                int loop_length = (i == cost_length-1)? remainder : 5;

                for(int j = 0; j < loop_length; j++) {
                    switch(minerals[i*5+j]){

보면 몫과 나머지를 이용해서 풀려고 하였고, 구간 별 값 또한 길이가 정해진 배열을 이용해서 풀려고 하였다. 배열의 길이는 구간/5 나머지가 있으면 구간/5 +1 로 두었다. 굳이 배열을 선택해서 문제를 더 어렵게 만들었다.
List를 사용하면 엄청 느릴 거라는 막연한 생각이 List 사용을 막은 것 같다. ArrayList()의 삽입은 공간이 다 차서 새로운 메모리를 할당하는 순간이 아닌 한 O(1)로 배열과 동일하다. (ArrayList는 배열로 구현한 것이라서 방금 설명한 공간이 모두 차서 새로운 ArrayList 공간을 추가해야 하는 상황이 아니라면 조회, 삭제,삽입에 있어서 모든 시간 복잡도가 같다.) 그러니, ArrayList 사용을 그렇게 꺼릴 필요는 없을 것 같다.

공부한 링크 : 블로그