[프로그래머스] 광물 캐기(Java), 그리디 알고리즘

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

프로그래머스

---

문제 풀이

그리디 알고리즘을 사용해 풀이 : 가장 피로가 높은 광물을 가장 효율적인 곡괭이로 캔다

 

 

1. 1개의 곡괭이로 5개의 광물을 캘 수 있으므로, 피로가 높은 광물을 나열할때 5개의 광물 묶음으로 만든 리스트를 만들어준다.

    // 5개의 광물 묶음
    static class Mineral {
        private int diamond;
        private int iron;
        private int stone;
        
        public Mineral(int diamond, int iron, int stone) {
            this.diamond = diamond;
            this.iron = iron;
            this.stone = stone;
        }
    }

	// 5개의 광물 묶음(Mineral) 리스트 생성
	List<Mineral> mineralList = new ArrayList<>(); 
        
        for(int i=0; i<minerals.length; i+=5) {
            int dia = 0; int iron = 0; int stone = 0;
            
            for(int j=i; j<i+5; j++) {
                if(j == minerals.length) {
                    break;
                }
                
                if("diamond".equals(minerals[j])) {
                    dia++;
                } else if("iron".equals(minerals[j])) {
                    iron++;
                } else if("stone".equals(minerals[j])) {
                    stone++;
                }
            }
            
            mineralList.add(new Mineral(dia, iron, stone));

 

2. 광물 묶음을 피로도가 높은 순서대로 나열해준다.

이때, 묶음 안의 다이아몬드 수만을 기준으로 리스트를 정렬했다가 잘못된 정답이 나왔다. (주석 참고)

다이아몬드 수가 같을 경우도 고려한 정렬이 필요하다. -> 다이아몬드 수가 같을 경우, 철의 수를 기준으로 정렬

        // 가장 피로도가 높은 다이아몬드 수를 기준으로 5개 묶은 광물 리스트를 정렬
        //Collections.sort(mineralList, ((o1, o2) -> (o2.diamond - o1.diamond)));
        
        Collections.sort(mineralList, new Comparator<Mineral>() {
            @Override
            public int compare(Mineral o1, Mineral o2) {
                if(o1.diamond - o2.diamond == 0){
                    return o2.iron - o1.iron;
                }
                return o2.diamond - o1.diamond;
            }
        });

 

3. 광물 묶음 리스트에 따른 피로도 계산 : 다이아몬드 곡괭이 -> 철 곡괭이 -> 돌 곡괭이 순서로 진행

        int diaPick = picks[0]; int ironPick = picks[1]; int stonePick = picks[2]; // 곡괭이 수
        
        for(Mineral m : mineralList) {
            int diamond = m.diamond; int iron = m.iron; int stone = m.stone; // 묶음 안에 있는 광물 수
            
            // 다이아몬드 곡괭이
            if(diaPick > 0) {
                answer += diamond;
                answer += iron;
                answer += stone;
                diaPick--;
                continue;
            }
            
            // 철 곡괭이
            if(ironPick > 0) {
                answer += diamond * 5;
                answer += iron;
                answer += stone;
                ironPick--;
                continue;
            }
            
            // 돌 곡괭이
            if(stonePick > 0) {
                answer += diamond * 25;
                answer += iron * 5;
                answer += stone;
                stonePick--;
                continue;
            }
        }

 

위와 같이 실행해 제출한 결과, 테스트케이스 8번을 제외하고 통과하였다.

검색해보니 곡괭이가 다 떨어질 경우 광물을 캘 수 없는 경우를 고려해야 한다고 해서 광물 묶음 리스트를 만들어 줄 때, 곡괭이가 다 떨어졌을 경우 break를 걸었다. -> 가지고 있는 곡괭이로 캘 수 있는 광물의 수까지만 for문을 돌리며 광물 묶음 리스트에 담아준다.

 

최종 코드는 아래와 같다.

import java.util.*;

class Solution {
    
    // 5개의 광물 묶음
    static class Mineral {
        private int diamond;
        private int iron;
        private int stone;
        
        public Mineral(int diamond, int iron, int stone) {
            this.diamond = diamond;
            this.iron = iron;
            this.stone = stone;
        }
    }
    
    public int solution(int[] picks, String[] minerals) {
        int diaPick = picks[0]; int ironPick = picks[1]; int stonePick = picks[2]; // 곡괭이 수
        int totalPickNum = diaPick + ironPick + stonePick; // 총 곡괭이 수
        int answer = 0;
        
        // 미네랄을 5개묶음으로 묶은 리스트 생성
        List<Mineral> mineralList = new ArrayList<>(); 
        
        for(int i=0; i<minerals.length; i+=5) {
            int dia = 0; int iron = 0; int stone = 0;
            
            if(totalPickNum == 0) {
                break;
            }
            
            for(int j=i; j<i+5; j++) {
                if(j == minerals.length) {
                    break;
                }
                
                if("diamond".equals(minerals[j])) {
                    dia++;
                } else if("iron".equals(minerals[j])) {
                    iron++;
                } else if("stone".equals(minerals[j])) {
                    stone++;
                }
            }
            totalPickNum -= 1;
            
            mineralList.add(new Mineral(dia, iron, stone));   
        }
        
        // 가장 피로도가 높은 다이아몬드 수를 기준으로 5개 묶은 광물 리스트를 정렬
        //Collections.sort(mineralList, ((o1, o2) -> (o2.diamond - o1.diamond)));
        
        Collections.sort(mineralList, new Comparator<Mineral>() {
            @Override
            public int compare(Mineral o1, Mineral o2) {
                if(o1.diamond - o2.diamond == 0){
                    return o2.iron - o1.iron;
                }
                return o2.diamond - o1.diamond;
            }
        });
        
        for(Mineral m : mineralList) {
            int diamond = m.diamond; int iron = m.iron; int stone = m.stone; // 묶음 안에 있는 광물 수
            
            // 다이아몬드 곡괭이
            if(diaPick > 0) {
                answer += diamond;
                answer += iron;
                answer += stone;
                diaPick--;
                continue;
            }
            
            // 철 곡괭이
            if(ironPick > 0) {
                answer += diamond * 5;
                answer += iron;
                answer += stone;
                ironPick--;
                continue;
            }
            
            // 돌 곡괭이
            if(stonePick > 0) {
                answer += diamond * 25;
                answer += iron * 5;
                answer += stone;
                stonePick--;
                continue;
            }
        }
        
        return answer;
    }
}