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

풀이: 

1. 알고리즘 파악

처음에는 "곡괭이를 하나 고르고 -> 5개 캐고 -> 다음 곡괭이 고르고..." 이렇게 가지치기하듯(트리 순회) 모든 경우를 다 따져보는 방식을 생각했다. 하지만 이 문제에는 규칙이 있다.                                    

• 규칙: 곡괭이를 하나 들면 무조건 광물 5개를 연속으로 캐야 합니다.
• 핵심: 광물의 순서는 바꿀 수 없지만, 어떤 곡괭이를 먼저 쓸지는 우리가 정할 수 있습니다.

따라서 굳이 모든 트리를 다 돌 필요 없이, "가장 딱딱하고 비싼 광물이 뭉쳐 있는 구간에 가장 좋은 곡괭이를 쓴다"는 전략(그리디)을 쓰면 훨씬 쉬울 것 같다.

2. 알고리즘 설계 (로직 구성)

1. 끊어 읽기: 광물을 5개씩 묶어서 하나의 '그룹'으로 생성
2. 가중치 계산: 각 그룹을 캘 때 '가장 안 좋은 곡괭이(돌 곡괭이)'로 캔다면 피로도가 얼마나 들지 계산 (그 그룹의 '난이도')
   • 다이아몬드는 가중치 25, 철은 5, 돌은 1
3. 커트라인: 가진 곡괭이 수로 캘 수 있는 광물까지만 계산 곡괭이가 없는데 광물만 남으면 의미x
4. 정렬(Sorting): 피로도(난이도)가 가장 높은 그룹부터 내림차순으로 정렬합
5. 배정: 가장 난이도가 높은 그룹에 다이아 곡괭이 -> 철 곡괭이 -> 돌 곡괭이 순서로 사용

---

3. Java 코드 구현 

import java.util.*;

class Solution {
    
    // 1. 광물 5개 묶음을 저장할 클래스 생성
    static class MineralGroup {
        int diamondCount;
        int ironCount;
        int stoneCount;
        int totalFatigue; // 돌 곡괭이 기준 피로도 총합 (이 그룹의 난이도)

        public MineralGroup(int diamondCount, int ironCount, int stoneCount) {
            this.diamondCount = diamondCount;
            this.ironCount = ironCount;
            this.stoneCount = stoneCount;
            // 돌 곡괭이로 캘 때의 피로도: 다이아는 25, 철은 5, 돌은 1
            this.totalFatigue = (diamondCount * 25) + (ironCount * 5) + (stoneCount * 1);
        }
    }

    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        int totalPicks = picks[0] + picks[1] + picks[2]; // 총 곡괭이 수
        
        // 2. 캘 수 있는 광물의 한계 설정
        // 광물 배열의 길이와 (곡괭이 수 * 5)
        int targetLength = Math.min(minerals.length, totalPicks * 5);
        
        List<MineralGroup> groups = new ArrayList<>();

        // 3. 광물을 5개씩 묶어서 리스트에 저장
        for (int i = 0; i < targetLength; i += 5) {
            int dia = 0, iron = 0, stone = 0;
            
            // 5개씩 묶되, 배열 범위를 넘지 않도록 체크
            for (int j = i; j < i + 5 && j < targetLength; j++) {
                if (minerals[j].equals("diamond")) dia++;
                else if (minerals[j].equals("iron")) iron++;
                else if (minerals[j].equals("stone")) stone++;
            }
            
            groups.add(new MineralGroup(dia, iron, stone));
        }

        // 4. 피로도가 높은(어려운) 그룹 순서대로 정렬 (내림차순)
        groups.sort((o1, o2) -> o2.totalFatigue - o1.totalFatigue);

        // 5. 좋은 곡괭이부터 순서대로 사용하여 피로도 계산
        // picks[0]: 다이아, picks[1]: 철, picks[2]: 돌
        for (MineralGroup group : groups) {
            if (picks[0] > 0) { // 다이아 곡괭이 사용
                answer += (group.diamondCount * 1) + (group.ironCount * 1) + (group.stoneCount * 1);
                picks[0]--;
            } else if (picks[1] > 0) { // 철 곡괭이 사용
                answer += (group.diamondCount * 5) + (group.ironCount * 1) + (group.stoneCount * 1);
                picks[1]--;
            } else if (picks[2] > 0) { // 돌 곡괭이 사용
                answer += (group.diamondCount * 25) + (group.ironCount * 5) + (group.stoneCount * 1);
                picks[2]--;
            } else {
                break; // 곡괭이 다 씀
            }
        }

        return answer;
    }
}

 

4. 팁 

1. 클래스(Class) 활용하기:
   • 위 코드의 MineralGroup처럼, 서로 연관된 데이터(다이아 개수, 철 개수, 피로도 등)를 묶어서 하나의 객체로 관리하면 코드가 훨씬 깔끔해짐 
2. Collections.sort()와 람다식:
   • groups.sort((o1, o2) -> o2.totalFatigue - o1.totalFatigue);
   • 이 부분은 "o2(뒤에 것)의 피로도가 크면 앞으로 보내라"는 뜻으로, 내림차순 정렬 공식처럼 외워두면 좋다. (오름차순은 o1 - o2)

 

---

문재 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/172927?language=java