[PS] 99클럽 코테 스터디 39일차 TIL (광물 캐기)

문제

문제 링크

설명

세 종류의 곡괭이가 있고, 광물의 종류에 따라 각 곡괭이의 피로도가 다르게 책정되어 있다. 각 곡괭이의 갯수가 배열로 주어지고 광물의 종류가 배열로 주어질때 곡괭이를 모두 소모하거나, 광물을 모두 캐는 경우의 피로도 최소값을 반환하는 문제

풀이

1. 그룹화 : 한 곡괭이 당 어떤 광물이 되었든간에 5번밖에 사용할 수 없다. 따라서 광물을 5개씩 그룹을 나눠 각 그룹에서의 가장 효율적인(피로도가 낮은) 곡괭이를 선택해야 한다. 예를 들어, 첫번째 예시에서 다음과 같이 그룹화 할 수 있다.

   group1 = ["diamond", "diamond", "diamond", "iron", "iron"]
   group2 = ["diamond", "iron", "stone"]
   

2. 가중치 계산 : 이제 저 그룹들을 소화할 곡괭이만 선택하면 된다. 여기서 선택기준은 광물 가중치가 제일 큰 그룹에 강력한 곡괭이를 사용해야 한다. 각 그룹의 광물 가중치를 계산하기 위해 문제에서 주어지는 곡괭이 피로도를 저장하고 있는 배열을 만든 뒤, 그룹마다 다이아몬드 곡괭이가 소모하는 피로도, 철 곡괭이가 소모하는 피로도, 돌 곡괭이가 소모하는 피로도를 합산해 sum 에 저장시켜 둔다. 5개씩 몇개의 그룹이 나오는지 확인하기 위해 5로 나눈 몫 만큼 반복을 하고, 나머지 광물들에 대해서도 가중치를 계산해서 저장한다.

3. 최소 피로도 출력 : 그룹 별 총 피로도(가중치) 가 저장되어 있는 sum 리스트를 반복문으로 돌리면서 각 그룹에 곡괭이를 할당 해야 한다.
   • 가장 큰 가중치를 가진 그룹에 다이아몬드 곡괭이부터 할당하기 위해 sum 리스트를 내림차순 정렬한 뒤 반복문을 돌린다.
4. 문제 제한 사항 확인 : 처음에 int length = minerals.length 로 제출했었는데 8번 테스트케이스를 통과하지 못했다. 문제에 더 사용할 곡괭이가 없거나 광산에 있는 모든 광물을 캘 때까지 과정을 반복 하라고 했기 때문에 광물의 갯수 뿐만 아니라 현재 가지고 있는 곡괭이로 캘 수 있는 광물의 갯수도 같이 생각해야 한다.
   • 광물을 모두 캔 경우 : minerals.length
   • 모든 곡괭이를 사용한 경우 : (picks[0] + picks[1] + picks[2]) * 5
   • 위 두가지 케이스 중 더 작은 수 만큼밖에 작업을 하지 못하므로 Math.min(minerals.length, (picks[0] + picks[1] + picks[2]) * 5) 로 length 를 정의해야 한다.

class Solution {
  static class Pick implements Comparable<Pick> {
    int diamondPick;
    int ironPick;
    int stonePick;

    public Pick(int diamondPick, int ironPick, int stonePick) {
      this.diamondPick = diamondPick;
      this.ironPick = ironPick;
      this.stonePick = stonePick;
    }

    @Override
    public int compareTo(Pick o) {
      return (o.diamondPick + o.ironPick + o.stonePick) - (this.diamondPick + this.ironPick + this.stonePick);
    }
  }

  public int solution(int[] picks, String[] minerals) {
    int answer = 0;
    int[][] fatigue = new int[3][3];
    fatigue[0] = new int[]{1, 1, 1};
    fatigue[1] = new int[]{5, 1, 1};
    fatigue[2] = new int[]{25, 5, 1};


    int length = Math.min(minerals.length, (picks[0] + picks[1] + picks[2]) * 5);
    int q = length / 5;
    int r = length % 5;
    ArrayList<Pick> sum = new ArrayList<>();

    for (int i = 0; i < q; i++) {
      int diamondPick = 0, ironPick = 0, stonePick = 0;
      for (int j = 0; j < 5; j++) {
        if (minerals[i * 5 + j].equals("diamond")) {
          diamondPick += fatigue[0][0];
          ironPick += fatigue[1][0];
          stonePick += fatigue[2][0];
        } else if (minerals[i * 5 + j].equals("iron")) {
          diamondPick += fatigue[0][1];
          ironPick += fatigue[1][1];
          stonePick += fatigue[2][1];
        } else {
          diamondPick += fatigue[0][2];
          ironPick += fatigue[1][2];
          stonePick += fatigue[2][2];
        }
      }
      sum.add(new Pick(diamondPick, ironPick, stonePick));
    }

    if (r != 0) {
      int diamondPick = 0, ironPick = 0, stonePick = 0;
      for (int i = 0; i < r; i++) {
        if (minerals[q * 5 + i].equals("diamond")) {
          diamondPick += fatigue[0][0];
          ironPick += fatigue[1][0];
          stonePick += fatigue[2][0];
        } else if (minerals[q * 5 + i].equals("iron")) {
          diamondPick += fatigue[0][1];
          ironPick += fatigue[1][1];
          stonePick += fatigue[2][1];
        } else {
          diamondPick += fatigue[0][2];
          ironPick += fatigue[1][2];
          stonePick += fatigue[2][2];
        }
      }
      sum.add(new Pick(diamondPick, ironPick, stonePick));
    }

    Collections.sort(sum);

    for (Pick p : sum) {
      if (picks[0] > 0) {
        answer += p.diamondPick;
        picks[0]--;
      } else if (picks[1] > 0) {
        answer += p.ironPick;
        picks[1]--;
      } else if (picks[2] > 0) {
        answer += p.stonePick;
        picks[2]--;
      } else {
        break;
      }
    }
    return answer;
  }
}