[프로그래머스/Level2] 광물 캐기 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 그리디

1. 연속된 5개의 광물을 한 그룹으로 묶어 각각 다이아/철/돌 곡괭이로 캤을 경우의 피로도의 합을 그룹별로 저장한다.

2. 돌로 캤을 때 가장 피로도가 높은 순으로 내림차순 정렬한다.

3. 정렬 후, 다이아 - 철 - 돌 곡괭이 순으로 캐야 피로도를 최소화할 수 있다.

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        
        int cnt = Math.min(minerals.length/5 +1, picks[0]+picks[1]+picks[2]); // 곡괭이 수
        int[][] 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) { // 5개씩
            if(i/5 == cnt) // 곡괭이 수가 광물을 5개씩 묶은 그룹 수보다 적은 경우 탈출
                break;
            
            for(int j = i ; j < i+5 ; j++) {
                if(minerals[j].equals("diamond")) {
                    dp += 1;
                    ip += 5;
                    sp += 25;
                }
                else if(minerals[j].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;
    }
}

 

 

 

➕ 다른 풀이 방식

백트래킹을 사용할 수도 있다고 한다.

1) 백트래킹으로 곡괭이들 조합을 구한다.

2) 곡괭이 조합으로 모든 경우의 cost를 구해 minCost를 구한다.

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

 

---

💦 어려웠던 점

- 처음 아이디어 : picks배열을 돌면서 minerals배열을 5개씩 끊어서 캐도록 생각했었다.

 

 

 

🧐 새로 알게 된 내용

다,,, 복습을 열심히 해야겄다!

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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

 

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

 

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