[Programmers] 172927. 광물 캐기 (java)

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

 

 

문제 파악

• 주어진 정보/입력
  • 각 곡괭이로 광물을 캘 때의 피로도가 표로 주어진다.
  • 광물은 주어진 순서대로만 캘 수 있다.
  • 한 곡괭이를 선택하면, 해당 곡괭이로 광물 5개를 연속으로 캐야 한다.
  • 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캔다.
  • 입력값: 마인이 갖고 있는 곡괭이의 개수를 나타내는 정수 배열 picks와, 광물들의 순서를 나타내는 문자열 배열 minerals
  • 제한사항: picks는 [dia, iron, stone]과 같은 구조로 이루어져 있다.
• 해결해야 하는 문제
  • 마인이 작업을 끝내기까지 필요한 최소한의 피로도를 return

 

문제 풀이

Greedy

import java.util.*;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        
        int[][] power = {
            {1, 1, 1},
            {5, 1, 1},
            {25, 5, 1}
        };
        
        // 광물 5개씩 묶기
        int pickCount = picks[0] + picks[1] + picks[2];
        int mineralLimit = Math.min(minerals.length, pickCount * 5);
        List<Chunk> chunks = new ArrayList<>();
        
        for (int i = 0; i < mineralLimit; i += 5) {
            int dia = 0, iron = 0, stone = 0;
            for (int j = i; j < i + 5 && j < mineralLimit; j++) {
                if (minerals[j].equals("diamond")) ++dia;
                else if (minerals[j].equals("iron")) ++iron;
                else ++stone;
            }
            chunks.add(new Chunk(dia, iron, stone));
        }
        
        chunks.sort((c1, c2) -> c2.getWeight() - c1.getWeight());
        
        int answer = 0;
        for (Chunk chunk : chunks) {
            for (int i = 0; i < 3; i++) {
                if (picks[i] == 0) continue;
                
                answer += power[i][0] * chunk.dia + power[i][1] * chunk.iron + power[i][2] * chunk.stone;
                --picks[i];
                break;
            }
        }
        
        return answer;
    }
    
    class Chunk {
        int dia;
        int iron;
        int stone;
        
        Chunk(int dia, int iron, int stone) {
            this.dia = dia;
            this.iron = iron;
            this.stone = stone;
        }
        
        int getWeight() {
            return dia * 25 + iron * 5 + stone;
        }
    }
}

 

📊 실행 결과

 

 

NOTE

• 첫번째 시도는 문제 조건 중 "5개씩 묶어 처리"와 "곡괭이 배정 최적화"를 만족하지 않았음
• 문자열 비교는 ==이 아니라 equals
• 가중치가 높은 순으로 정렬하는 이유: 좋은 곡괭이를 좋은 묶음에 써야 피로도를 최소화할 수 있기 때문!
• 아래 문법 기억해두기

List<MineSet> chunks = new ArrayList<>();  
chunks.sort((a, b) -> b.getWeight() - a.getWeight());

• int mineralLimit = Math.min(minerals.length, pickCount * 5); 해줘야 하는 이유
• => 주어진 곡괭이로 모든 광물을 캘 수 있다고 가정하고 chunk를 만들어 버리고 정렬하면, 안 돼!
• => 주어진 곡괭이로 캘 수 있는 광물까지만 chunk 만들어야 해. 정렬해서 순서가 뒤바뀌어 버릴 테니까.