[pro] 프로그래머스 level2 172927 광물 캐기 (Java) - 그리디

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/172927

프로그래머스

 

[풀이]

광물은 순서대로 캐야하고, 하나의 곡괭이를 이용해 5개의 연속된 광물을 캐야 한다.

 

1. 5개씩 광물의 섹션을 묶어서 다이아 곡괭이, 철 곡괭이, 돌 곡괭이로 각각 캤을 경우의 피로도의 합을 섹션별로 저장해둔다.  

2. 돌로 캤을 때 가장 피로도가 높은 순서대로 내림차순 정렬한다. 돌로 캤을 때 피로도가 높은 경우를 다이아 곡괭이로 캐야 함을 이해해야 한다. 즉, 이 내림차순 정렬에 대해서는 다이아->철->돌 곡괭이 순으로 캐야 피로도를 최소화할 수 있다.

3. 8번 테케를 틀리지 않기 위해서 고려해야 하는 경우는 곡괭이수가 광물을 5개씩 묶은 섹션 개수보다 적은 경우이다. 이 경우, 광물은 순서대로 캐야 하므로 뒤에 있는 광물은 어차피 못캔다. 따라서 계산해서 저장하지 않고 break문으로 빠져나와야 한다. (돌 곡괭이로 캤을 때 피로도가 높아도 어차피 못캐는 경우이기 때문에 계산에 포함되지 않게 주의)

 

 

[코드]

 

package greedy;

import java.util.*;

class Pro_level2_172927 {
    static int[][] section;
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        //마인이 작업을 끝내기까지 필요한 최소한의 피로도를 return
        
        int cnt = Math.min(minerals.length/5+1, picks[0]+picks[1]+picks[2]);
        section = new int[cnt][3]; //5개씩 묶었을 때 광물별 피로도 계산
        int dp=0, ip=0, sp=0;
        int idx = 0;
        
        //곡괭이 개수만큼만 세기 -> 어차피 곡괭이 수가 부족하면 뒤에 있는 광물은 못 캠.
        for(int i=0; i<minerals.length; i+=5){   
            if(i/5==cnt){
                break;
            }
            for(int j=i; j<i+5; j++){

                String m = minerals[j]; 
                if(m.equals("diamond")){
                    dp += 1;
                    ip += 5;
                    sp += 25;
                }
                else if(m.equals("iron")){
                    dp += 1;
                    ip += 1;
                    sp += 5;
                }
                else{
                    dp += 1;
                    ip += 1;
                    sp += 1;
                }
                
                if(j==minerals.length-1){
                    break;
                }
            
            }
            
            section[i/5][0] = dp;
            section[i/5][1] = ip;
            section[i/5][2] = sp;
            
            dp = ip = sp = 0;
        }
        
    

        //돌로 캤을 때 피로도가 가장 높은 순으로 내림차순 정렬
        Arrays.sort(section, (o1, o2) -> (o2[2]-o1[2]));
        
        //다이아 -> 철 -> 돌 순서대로 캐기
        for(int i=0; i<cnt; i++){
            if(picks[0]!=0){
                answer += section[i][0]; //다이아로 캤을 때 피로도
                picks[0]--;
            }
            else if(picks[1]!=0){
                answer += section[i][1];
                picks[1]--;
            }
            else if(picks[2]!=0) {
                answer += section[i][2];
                picks[2]--;
            }                
        }
        
        return answer;
    }
}