[그리디] - Lv2 - 광물 캐기

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

프로그래머스

 

 

📌- 풀이

처음은 완전탐색을 하면 되지 않을까 생각해서 완전 탐색으로 문제를 풀다가 아니다 싶어서 다른 방법을 찾아봄

 

핵심적인 풀이법은

1. 광물을 5개씩 집단을 만들어서 각자 다이아, 철, 돌로 캤을 때의 값들을 만듬
2. 1번에서 나온 값들로 집단 마다 객체를 만들어서 list에 삽입
   이렇게 만들면 
   ex) list에 Mineral 객체 => (30, 50, 80) 이렇게 list에 쌓이게 됨
3.  가장 중요한 부분은 최솟값을 구하는 문제이므로 각 집단에서 돌을 기준으로 내림차순 정렬을 함
   
   돌로 내림차순 정렬을 하는 이유는
   예를 들어서 두 개의 집단이 있을 때 돌로 캤을 때의 비용이 각각 180, 100이라면
   180이 나온 집단을 다이아 곡괭이나 철 곡괭이로 캤을 때, 비용이 더 절감되기 때문
    
4. 정렬된 집단을 기준으로 다이아 곡괭이부터 하나씩 써가면서 곡괭이를 다 쓸때까지 결과값에 더하면 최솟값이 나옴

 

여기서 어려웠던 부분은 처음 정렬할 기준을 찾는 것이 어려웠음

 

 

🚨 - 주의할 점

처음 문제를 풀고 제출을 했을 때 계속 테스트케이스 1개가 틀려서 뭔지 찾아봤는데,

 

예를 들자면

 

곡괭이가 2개이고, 집단의 수가 3개 이상일 경우

-> 3개의 집단을 정렬하는 것이 아니라, 마지막 집단을 버리고 앞의 2개의 집단을 정렬해서 계산해야 함
     여기서 list를 슬라이싱해서 정렬을 해줘야 한다. 

 

이런 예외케이스가 있어서 이 부분에서도 시간을 많이 썼다.

 

 

 

 

🔥 - Java 코드

 

import java.util.*;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        
        int[][] arr = new int[][]{{1,1,1},{5,1,1},{25,5,1}};
        List<Mineral> list = new ArrayList<>();
        int total_number = 0;
        
        for(int m : picks){ // 광물 집합의 개수 보다 곡괭이의 개수가 적을 때를 위해 total_number 만듬
            total_number += m;
        }
        
        for(int i=0;i<(minerals.length/5) + 1 ;i++){
            
            int dia = 0;
            int iron = 0;
            int stone = 0;
            
        
            for(int j=i*5;j<(i*5)+5 && j<minerals.length;j++){
                int num =0;
                
                switch(minerals[j].charAt(0)){
                        
                    case 'd':
                        dia += arr[0][num];
                        iron += arr[1][num];
                        stone += arr[2][num];
                        break;
                    case 'i':
                        num=1;
                        dia += arr[0][num];
                        iron += arr[1][num];
                        stone += arr[2][num];
                        break;
                    case 's':
                        num=2;
                        dia += arr[0][num];
                        iron += arr[1][num];
                        stone += arr[2][num];
                        break;
                        
                
                }
            }
            list.add(new Mineral(dia,iron,stone));
        }
        
        if(total_number < list.size()){ // 곡괭이가 집단의 수보다 적을 때 예외처리, 슬라이싱
         list = list.subList(0,total_number);   
        }     
        list.sort(((o1, o2) -> (o2.stone - o1.stone)));
    
        for(Mineral m : list) {
			int diamond = m.diamond;
			int iron = m.iron;
			int stone = m.stone;
            
			if(picks[0] > 0) {
				answer += diamond;
				picks[0]--;
				continue;
			}

			if(picks[1] > 0) {
				answer += iron;
				picks[1]--;
				continue;
			}

			if(picks[2] > 0) {
				answer += stone;
				picks[2]--;
			}
            
		}
        return answer;
    }
    
    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;
		}
	}
    
}