🔥[99클럽 코테 스터디] 39일차 TIL - 광물 캐기

⏳문제

마인은 곡괭이로 광산에서 광석을 캐려고 합니다. 마인은 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이를 각각 0개에서 5개까지 가지고 있으며, 곡괭이로 광물을 캘 때는 피로도가 소모됩니다. 각 곡괭이로 광물을 캘 때의 피로도는 아래 표와 같습니다.

예를 들어, 철 곡괭이는 다이아몬드를 캘 때 피로도 5가 소모되며, 철과 돌을 캘때는 피로도가 1씩 소모됩니다. 각 곡괭이는 종류에 상관없이 광물 5개를 캔 후에는 더 이상 사용할 수 없습니다.

마인은 다음과 같은 규칙을 지키면서 최소한의 피로도로 광물을 캐려고 합니다.

• 사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캡니다.
• 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다.
• 광물은 주어진 순서대로만 캘 수 있습니다.
• 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캡니다.

즉, 곡괭이를 하나 선택해서 광물 5개를 연속으로 캐고, 다음 곡괭이를 선택해서 광물 5개를 연속으로 캐는 과정을 반복하며, 더 사용할 곡괭이가 없거나 광산에 있는 모든 광물을 캘 때까지 과정을 반복하면 됩니다.

마인이 갖고 있는 곡괭이의 개수를 나타내는 정수 배열 picks와 광물들의 순서를 나타내는 문자열 배열 minerals가 매개변수로 주어질 때, 마인이 작업을 끝내기까지 필요한 최소한의 피로도를 return 하는 solution 함수를 완성해주세요.

---

✏️풀이

피로도의 범위와 곡괭이의 정보가 정해져 있고, 최선의 선택을 구해야 하기 떄문에 그리디 방법으로 문제에 접근을 하였다.

곡괭이 하나로 광물 5개를 연속으로 캐기 때문에, 광물을 5개씩 그룹지어 각 그룹의 피로도 총합을 계산해 내림차순으로 정렬 후, 가장 피로도가 높은 그룹부터 차례대로 처리하는 방식으로 구현해 보았다.

광물 그룹화 및 피로도 계산

for (int i = 0; i < Math.min(totalPicks * 5, totalMinerals); i += 5) {
	int sum = 0; // 현재 그룹의 피로도
	int damage = 0; // 각 광물에 대한 피로도

	for (int j = i; j < Math.min(i + 5, totalMinerals); j++) {
		switch (minerals[j]) {
			case "diamond":
				damage = 25;
				break;
			case "iron":
				damage = 5;
				break;
			case "stone":
				damage = 1;
				break;
		}
        sum += damage; // 피로도 총합 업데이트
        mineralsGroup[i / 5][j % 5 + 1] = damage; // 각 광물의 피로도 저장
    }
	mineralsGroup[i / 5][0] = sum; // 현재 그룹의 총 피로도 저장
}

주어진 minerals 배열을 5개씩 그룹지어 피로도를 계산해야 하는데,
여기서 주의할 점은 전체 곡괭이의 개수에 5를 곱한 수와 minerals의 전체 길이 중 더 작은 값이 캘 수 있는 광물의 최대 개수라는 것이다. 즉, 만약 사용할 수 있는 곡괭이가 많더라도, 실제로 캐야 할 광물이 없다면 루프는 그만큼만 반복되어야 한다.

switch문을 사용하여 광물의 종류에 따라 피로도를 설정하고, sum에 피로도를 누적해 mineralsGroup[i / 5][0]에 현재 그룹의 총 피로도를 저장하고, mineralsGroup[i / 5][j % 5 + 1]에 각 광물의 피로도를 저장해준다.

피로도 기준으로 정렬

Arrays.sort(mineralsGroup, (o1, o2) -> o2[0] - o1[0]);

mineralsGroup을 총 피로도 기준으로 내림차순 정렬한다. 이렇게 하면 가장 피로도가 높은 그룹부터 차례로 처리할 수 있다.

곡괭이 사용 및 피로도 계산

for (int i = 0; i < totalPicks; i++) {
      int[] temp = mineralsGroup[i];
      String pick = "";
            
      if (dia > 0) {
           dia -= 1;
           pick = "diamond";
      }
      else if (iron > 0) {
           iron -= 1;
           pick = "iron";
      }
      else if (stone > 0) {
           stone -= 1;
           pick = "stone";
      }

이제 각 곡괭이를 사용한다.
사용 가능한 곡괭이 중에서 다이아몬드 곡괭이를 우선적으로 사용하고, 그다음으로 철 곡괭이, 돌 곡괭이 순으로 사용한다.
사용한 곡괭이의 개수를 줄이고, 사용한 곡괭이를 pick에 저장한다.

광물별 피로도 계산

for (int j = 1; j < 6; j++) {
	switch (pick) {
         case "diamond":
          	answer += (int) Math.ceil(temp[j] / 25.0);
          	break;
         case "iron":
            answer += (int) Math.ceil(temp[j] / 5.0);
            break;
         case "stone":
            answer += temp[j];
            break;
         }
    }

사용한 곡괭이에 따라 각 광물의 피로도를 계산한다.
Math.ceil을 사용한 이유는 곡괭이의 특성에 따라 피로도가 다르게 적용되기 때문이다.

👾전체 코드

import java.util.*;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        
        int dia = picks[0]; // 다이아 곡괭이 개수
        int iron = picks[1]; // 철 곡괭이 개수
        int stone = picks[2]; // 돌 곡괭이 개수

        // 전체 곡괭이의 개수
        int totalPicks = dia + iron + stone;

        // 광석 총 개수
        int totalMinerals = minerals.length;

        // 5개씩 그룹화해서 피로도 계산
        int[][] mineralsGroup = new int[totalPicks][6];

        for (int i = 0; i < Math.min(totalPicks * 5, totalMinerals); i += 5) {
            int sum = 0; // 현재 그룹의 피로도
            int damage = 0; // 각 광물에 대한 피로도

            for (int j = i; j < Math.min(i + 5, totalMinerals); j++) {
                switch (minerals[j]) {
                    case "diamond":
                        damage = 25;
                        break;
                    case "iron":
                        damage = 5;
                        break;
                    case "stone":
                        damage = 1;
                        break;
                }
                sum += damage; // 피로도 총합 업데이트
                mineralsGroup[i / 5][j % 5 + 1] = damage; // 각 광물의 피로도 저장
            }
            mineralsGroup[i / 5][0] = sum; // 현재 그룹의 총 피로도 저장
        }

        // 피로도 합 기준으로 내림차순 정렬
        Arrays.sort(mineralsGroup, (o1, o2) -> o2[0] - o1[0]);

        for (int i = 0; i < totalPicks; i++) {
            int[] temp = mineralsGroup[i];
            String pick = "";
            
            // 사용한 곡괭이의 개수를 줄이고, 어떤 곡괭이를 사용했는 지 저장
            if (dia > 0) {
                dia -= 1;
                pick = "diamond";
            }
            else if (iron > 0) {
                iron -= 1;
                pick = "iron";
            }
            else if (stone > 0) {
                stone -= 1;
                pick = "stone";
            }

            // 광물별 피로도 계산
            for (int j = 1; j < 6; j++) {
                switch (pick) {
                    case "diamond":
                        answer += (int) Math.ceil(temp[j] / 25.0);
                        break;
                    case "iron":
                        answer += (int) Math.ceil(temp[j] / 5.0);
                        break;
                    case "stone":
                        answer += temp[j];
                        break;
                }
            }
        }        
        return answer;
    }
}

---

🔗문제 링크
💻Repository