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

프로그래머스

 

문제 설명

 

곡괭이 하나를 선택해서 광물 5개를 연속으로 캐고, 다음 곡괭이를 선택해서 5개를 연속으로 캐는 과정을 반복하여, 더 사용할 곡괭이가 없거나, 모든 광물을 캘 때까지 과정을 반복합니다.

마인이 갖고 있는 곡괭이의 개수를 나타내는 배열 picks와 광물들의 순서를 나타내는 문자열 배열 minerals가 매개변수로 주어질 때, 마인이 작업을 끝내기까지 필요한 최소한의 피로도를 return 하는 solution함수를 완성해주세요.

 

---

접근 방식

• minerals의 길이가 짧다.(0 <= minerals.length <= 50) -> 완전 탐색 가능
• 5개 광물마다 다이아, 철, 돌 곡괭이로 캘 경우를 고려하고, 그 다음 5개의 광물을 캘 때 이전의 피로도를 받아서 계산하기 때문에 -> DFS를 사용합니다.
• 무조건 연속 5개의 광물 캐야함 -> 광물을 5개 단위로 묶음
• 가진 곡괭이 개수로 캘 수 있을 때까지만 캡니다. -> 캘 수 없는 광물은 버림.  

 

풀이 과정

1. 전체 곡괭이 개수와 광물을 5개씩 묶었을 때 몇 묶음이 나오는지 구합니다.

    그 중 더 작은 값을 n에 넣어, 캘 수 있는 광물까지(n)의 개수를 구해줍니다.

int pickCnt = Arrays.stream(picks).sum();//곡괭이 개수
int bundle = (minerals.lenth-1)/5+1;//광물을 5개씩 묶음
//곡괭이개수와 광물묶음개수 중에 더 작은 걸로 선택
int n = Math.min(pickCnt,bundle);

 

>> 5묶음으로 묶을 때 왜 저렇게 나누지?

0

0 0

0 0 0

0 0 0 0

0 0 0 0 0

length=1~5까지 다 1묶음이 나와야 함.

그냥 (minerals.length/5)를 해주면 length=4까지는 0이 나오는데 5일때는 1이 나오기 때문에 같은 숫자로 맞춰주기 위해 → (minerals.length-1/5)

 

그리고, 저렇게만 해주면 0묶음이 되기 때문에 +1해서 1묶음으로 만들어 줍니다.

 

2. 광물 5개 묶음씩 자르고, 그 안에 다이아, 철, 돌을 몇 개씩 가지고 있는지 배열에 저장합니다.

    가진 곡괭이로 캘 수 있을 만큼까지만 저장합니다.

코드

//5개 묶음 당 -> 다이아, 철, 돌 몇 개씩 가지고 있는지 저장.
int[][] mins = new int[n][3];
//기본적으로 광물을 끝까지 저장하지만, 곡괭이 개수를 초과하지 않을 때까지 저장.
for(int i=0;i<minerals.length && i<5*n;i++){
    if(minerals[i].equals("diamond")) mins[i/5][0]++; //0:다이아 개수
    else if(minerals[i].equals("iron")) mins[i/5][1]++;//1:철 개수
    else mins[i/5][2]++;//2: 돌 개수
}

 

3. 이제 묶음 단위로 다이아, 철, 돌 곡괭이를 선택하는 방법을 달리하며 DFS 탐색을 해줍니다.

코드

//mins:광물 5개씩 묶음 별 각 광물 개수 / picks:곡괭이 개수 / depth:몇번째 묶음 / fitague:현재 피로도 
void dfs(int[][] mins, int[] picks, int depth, int fitague){
    
    if(depth==mins.length){//광물 끝까지 다 조사하면 끝냄.
        if(fitague<minFitague) minFitague=fitague;
        return;
    }
    
    //곡괭이는 다이아(0) -> 철(1) -> 돌(2) 순
    for(int i=0;i<picks.length;i++){
        if(picks[i]==0) continue;// i곡괭이가 없으면 다음 곡괭이로 넘어감.
        
        picks[i]--; //i곡괭이 사용
        dfs(mins,picks,depth+1,fitague+cntFitague(mins[depth],i));
        picks[i]++; //i곡괭이 사용하기 전으로 되돌림.
    }
}

 

4. 현재 피로도 계산함수 cntFitague

코드

//5개 광물 묶음을 pick곡갱이로 캘 때 피로도
int cntFitague(int[] min5, int pick){
    int fitague=0;
    
    //0:다이아, 1:철, 2:돌
    for(int i=0;i<min5.length;i++){//i:광물
        if(pick<=i) fitague+=min5[i]*1;//곡괭이가 광물보다 세거나 같을때
        else if(pick-i==1) fitague+=min5[i]*5;//곡괭이가 광물보다 1 약할때
        else fitague+=min5[i]*25;//곡괭이가 광물보다 2 약할 때 -> 돌 곡괭이로 다이아 캐려고 할 때
    }
    
    return fitague;
}

 

---

전체 코드

import java.util.*;
class Solution {
    int minFitague=Integer.MAX_VALUE;//최소 피로도
    public int solution(int[] picks, String[] minerals) {
        
        int pickCnt = Arrays.stream(picks).sum();//곡괭이 개수
        int bundle = (minerals.length-1)/5+1;//광물 5개씩 묶음 개수
        //5개 광물씩 잘랐을 때 몇 묶음의 광물이 있는지 와 비교해서 더 작은 걸로 선택
        int n = Math.min(pickCnt,bundle);
        
        //5개의 광물 당 -> 다이아 몇개, 철 몇 개, 돌 몇개 가지고 있는지
        int[][] mins = new int[n][3];
				//기본적으로 광물을 끝까지 저장하지만, 곡괭이 개수를 초과하지 않을 때까지 저장.
        for(int i=0;i<minerals.length && i<5*n;i++){
            if(minerals[i].equals("diamond")) mins[i/5][0]++;
            else if(minerals[i].equals("iron")) mins[i/5][1]++;
            else mins[i/5][2]++;
        }
        
        dfs(mins,picks,0,0);
        
        return minFitague;
    }
    //mins:광물 5개씩 묶음 별 각 광물 개수 / picks:곡괭이 개수 / depth:몇번째 묶음 / 현재 피로도 
    void dfs(int[][] mins, int[] picks, int depth, int fitague){
        
        if(depth==mins.length){//광물 끝까지 다 조사하면 끝냄.
            if(fitague<minFitague) minFitague=fitague;
            return;
        }
        
        //곡괭이는 다이아(0) -> 철(1) -> 돌(2) 순
        for(int i=0;i<picks.length;i++){
            if(picks[i]==0) continue;// i곡괭이가 없으면 다음 곡괭이로 넘어감.
            
            picks[i]--;
            dfs(mins,picks,depth+1,fitague+cntFitague(mins[depth],i));
            picks[i]++;
        }
    }
    
    //5개 광물 묶음을 pick곡갱이로 캘 때 피로도
    int cntFitague(int[] min5, int pick){
        int fitague=0;
        
        //0:다이아, 1:철, 2:돌
        for(int i=0;i<min5.length;i++){
            if(pick-i<=0) fitague+=min5[i]*1;//곡괭이가 광물보다 세거나 같을때
            else if(pick-i==1) fitague+=min5[i]*5;//곡괭이가 광물보다 1 약할때
            else fitague+=min5[i]*25;//곡괭이가 광물보다 2 약할 때 -> 돌 곡괭이로 다이아 캐려고 할 때
        }
        
        return fitague;
    }
}