[프로그래머스] 광물 캐기 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/172927?language=java

프로그래머스

광물 캐기 문제

각 곡괭이로 광물을 캤을 때 소비되는 피로도의 최소 값을 구하는 문제

 

#사용 알고리즘

그리디(greedy)

📌문제 접근 포인트

1. 광물을 캐기 전에 갖고 있는 곡괭이의 수를 먼저 확인하자. 곡괭이로 캘 수 있는 광물의 수는 연속 5개씩이므로, 그 이상 넘어가는 광물은 캐지 못한다.

2. 각 광물에 대해 필요한 피로도 수를 계산하자. 광물에 각 곡괭이별 소비되는 피로도 수를 모아보자.

3. 피로도 수를 모두 모았다면, 돌 곡괭이로 캤을 때의 피로도를 기준으로 내림차순으로 정렬하자. 가장 많은 피로도가 소모되는 수부터 다이아 곡괭이로 부숴나가면 최소의 피로도로 광물을 캘 수 있게 된다.

반응형

⚙ 내가 푼 정답 코드

import java.util.*;

class Solution {
    public static void cost(int[] costs, int a, int b, int c){ // 피로도 계산
        costs[0] += a;
        costs[1] += b;
        costs[2] += c;
    }
    
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        int sum = picks[0] + picks[1] + picks[2]; // 곡괭이 갯수
        int[][] p = new int[sum][3]; 
        
        for (int i = 0 ; i < minerals.length; i += 5){
            int n = i/5;
            if(n == sum){
                break;
            }
            int[] costs = new int[3];
            for (int j = i ; j < i+5; j++){
                if (j == minerals.length){ // 마지막에 5개가 안되는 경우
                    break;
                }
                String x = minerals[j];
                if (x.equals("diamond")){
                    cost(costs,1,5,25);
                }
                else if (x.equals("iron")){
                    cost(costs,1,1,5);
                }
                else {
                    cost(costs,1,1,1);
                }
            }
            for (int l = 0 ; l < 3; l++){
                p[n][l] = costs[l];
            }
            costs = new int[3];
        }
        
        Arrays.sort(p, (a1, a2) -> (a2[2]-a1[2]));
        
        for(int i = 0; i < sum; i++){
            if(picks[0] > 0){
                answer += p[i][0];
                picks[0]--;
            }
            else if(picks[1] > 0){
                answer += p[i][1];
                picks[1]--;
            }
            else if(picks[2] > 0){
                answer += p[i][2];
                picks[2]--;
            }
        }
        
        return answer;
    }
}