프로그래머스 level 2 - 광물 캐기 (Java)

• 문제 링크

1. 접근 방법

최소 피로도를 구하라고 했으니 백트랙킹을 써도 되겠지만, 문제의 표를 자세히 보면 뭔가 다른 방법으로 풀어도 될 것 같은 생각이 든다.

곡괭이 이하의 등급을 가진 광물을 캐면 피로도가 1이고, 광물의 등급이 하나씩 높아질 때마다 피로도가 5배씩 증가한다. 돌 광물만 연속으로 5개를 캐는 게 아닌 이상 돌 곡괭이보단 철 혹은 다이아 곡괭이로 캐는 게 피로도가 무조건 적게 들고, 마찬가지로 철 혹은 돌 광물만 캐는 게 아닌 이상, 즉 다이아 광물이 하나라도 포함돼 있으면 다이아 곡괭이로 캐는 게 피로도가 가장 적다.

광물은 무조건 연속으로 5개씩을 캐야 하고, 그 5개 중 가장 높은 등급의 광물보다 하위 등급의 곡괭이로 캐는 것은 손해이기 때문에 이를 계산에 반영할 수 있도록 가중치를 부여한다.

1. 광물을 5개씩 묶어서 한 묶음에 대한 가중치를 매긴다.

int[][] status = new int[slength][4];

setStatus(status, minerals);

slength은 광물의 개수/5 를 올림한 숫자다. 단 이 숫자가 곡괭이 개수보다 적으면 slength을 곡괭이 개수로 변경한다. 2번에서 status를 정렬하기 때문에, 이렇게 하지 않으면 광물을 순서대로 캔다는 조건에 맞지 않는 경우가 정답으로 도출될 수도 있다.

setStatus()에서 i번째 묶음 광물 5개의 상태를 status[i][0] ~ status[i][2]에 저장하고 status[i][3]에는 가중치를 저장한다.

가중치 = 25 x 다이아 광물 개수 + 5 x 철 광물 개수 + 돌 광물 개수

2. 그 가중치에 따라 status를 내림차순으로 정렬한다.

Arrays.sort(status, ((o1, o2) -> o2[3] - o1[3]));

즉 이 순서는 안 좋은 곡괭이를 쓸수록 피로도를 많이 잡아먹는 순서다.

3. 곡괭이를 좋은 거부터 하나씩 쓰면서 정렬된 status대로 광물을 캔다.

---

2. 코드

  import java.util.*;

  class Solution {
        public int solution(int[] picks, String[] minerals) {
            int fatigue = 0;
            int slength = (int) Math.ceil(minerals.length / 5.0);
            if (slength > picks[0] + picks[1] + picks[2]) slength = picks[0] + picks[1] + picks[2];
            int[][] status = new int[slength][4];

            setStatus(status, minerals);

            Arrays.sort(status, ((o1, o2) -> o2[3] - o1[3]));
            int pInd = 0, sInd = 0;
            while (pInd < picks.length) {
                if (picks[pInd] == 0) {
                    pInd++;
                    continue;
                }

                picks[pInd]--;
                if (pInd == 0) fatigue += status[sInd][0] + status[sInd][1] + status[sInd][2];
                else if (pInd == 1) fatigue += status[sInd][0] * 5 + status[sInd][1] + status[sInd][2];
                else fatigue += status[sInd][0] * 25 + status[sInd][1] * 5 + status[sInd][2];
                sInd++;
                if (sInd >= status.length) break;
            }

            return fatigue;
        }

        private void setStatus(int[][] status, String[] minerals) {
            int cnt = 0, ind = 0;
            for (int i = 0; i < minerals.length; i++) {
                cnt++;

                if (minerals[i].equals("diamond")) status[ind][0]++;
                else if (minerals[i].equals("iron")) status[ind][1]++;
                else status[ind][2]++;

                if (cnt == 5 || i == minerals.length - 1) {
                    cnt = 0;
                    status[ind][3] = 25 * status[ind][0] + 5 * status[ind][1] + status[ind][2];
                    ind++;
                }

                if (ind >= status.length) break;
            }
        }
    }