프로그래머스 172927번
https://school.programmers.co.kr/learn/courses/30/lessons/172927

문제

---

생각하기

---

• 그리디와 정렬 문제이다.

  • 캐야 하는 광물을 5개 단위로 잘라서 다이아몬드, 철, 돌 순으로 정렬한다.

    • 이유는 picks에서 곡괭이의 순서가 다이아몬드 -> 철 -> 돌 순서로 되어있기 때문

동작

        List<Mineral> mineralList = new ArrayList<>();
        int N = minerals.length;
        int M = picks[0] + picks[1] + picks[2];

        for (int i = 0; i < N && mineralList.size() < M; i += 5) {
            int d = 0, r = 0, s = 0;
            for (int j = i; j < Math.min(i + 5, N); j++) {
                char mineralType = minerals[j].charAt(0);
                if (mineralType == 'd') d++;
                else if (mineralType == 'i') r++;
                else s++;
            }
            mineralList.add(new Mineral(d, r, s));
        }
        
        
        // 다이아, 철, 돌이 많은순으로 정렬 -> picks에서 다이아몬드 곡괭이, 철 곡괭이 순으로 나오기 때문에
        Collections.sort(mineralList, Collections.reverseOrder());

광물들을 5개로 끊어 그룹 지은 객체를 담은 mineralList 생성

i < N && mineralList.size() < M; <- 끝나는 조건이 광물을 모두 캐서 없거나, 곡괭이를 모두 소모했을 때이므로 광물을 5개씩 그룹 지을 때도 이 조건이 들어가야 한다.

j < Math.min(i + 5, N); <- 5개씩 끊다 보면 5개가 되지 않고 남는 경우가 생길 수 있으므로 최솟값으로 j가 반복할 수 있도록 만듦

Collections.sort(mineralList, Collections.reverseOrder()); <- 그리고 picks[]의 순서가 다이아몬드, 철, 돌 순서로 되어있으므로 그리디 방식으로 생각했을 때, 다이아몬드 곡괭이로 다이아몬드가 가장 많은 그룹을 해야 최소한의 피로도로 채굴할 수 있기 때문에 정렬을 해준다.

        int ans = 0;
        int l = 0;
        for (Mineral m : mineralList) {
            while (l < 3 && picks[l] == 0) {
                l++; // 곡괭이 하나씩 소모 
            }
            if (l == 3) {
                break; // 곡괭이 다쓰면 종료    
            }
            
            ans += m.d * fatigues[l][0] + m.r * fatigues[l][1] + m.s * fatigues[l][2];
            picks[l]--;
        }

        return ans;

이제 정렬된 mineralList를 하나씩 꺼내서 picks[]배열을 모두 소모하거나, 더 이상 광물이 없을 때까지 피로도를 총합하면 결과를 얻을 수 있다.

결과

코드

---

import java.util.*;

class Solution {
    public static int[][] fatigues = {
        { 1, 1, 1 },
        { 5, 1, 1 },
        { 25, 5, 1 }
    };
    
    public static class Mineral implements Comparable<Mineral> {
        int d, r, s;

        public Mineral(int d, int r, int s) {
            this.d = d;
            this.r = r;
            this.s = s;
        }

        @Override
        public int compareTo(Mineral o) {
            if(d == o.d) {
                if(r == o.r) {
                    return s - o.s;
                }
                return r - o.r;
            }
            return d - o.d;
        }
    } // End of Mineral class
    
    public static int solution(int[] picks, String[] minerals) {
        List<Mineral> mineralList = new ArrayList<>();
        int N = minerals.length;
        int M = picks[0] + picks[1] + picks[2];


        for (int i = 0; i < N && mineralList.size() < M; i += 5) {
            int d = 0, r = 0, s = 0;
            for (int j = i; j < Math.min(i + 5, N); j++) {
                char mineralType = minerals[j].charAt(0);
                if (mineralType == 'd') d++;
                else if (mineralType == 'i') r++;
                else s++;
            }
            mineralList.add(new Mineral(d, r, s));
        }

        // 다이아, 철, 돌이 많은순으로 정렬 -> picks에서 다이아몬드 곡괭이, 철 곡괭이 순으로 나오기 때문에
        Collections.sort(mineralList, Collections.reverseOrder());
        
        int ans = 0;
        int l = 0;
        for (Mineral m : mineralList) {
            while (l < 3 && picks[l] == 0) {
                l++; // 곡괭이 하나씩 소모 
            }
            if (l == 3) {
                break; // 곡괭이 다쓰면 종료    
            }
            
            ans += m.d * fatigues[l][0] + m.r * fatigues[l][1] + m.s * fatigues[l][2];
            picks[l]--;
        }

        return ans;
    }
} // End of Solution class