프로그래머스 광물캐기(lvl2) 풀어보기

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/172927

프로그래머스

---

문제 핵심

• 사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캡니다.
• 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다.
• 광물은 주어진 순서대로만 캘 수 있습니다.
• 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캡니다.
• 곡괭이를 하나 선택해서 광물 5개를 연속으로 캐고, 다음 곡괭이를 선택해서 광물 5개를 연속으로 캐는 과정을 반복하며, 더 사용할 곡괭이가 없거나 광산에 있는 모든 광물을 캘 때까지 과정을 반복하면 됩니다.
• 마인이 갖고 있는 곡괭이의 개수를 나타내는 정수 배열 picks와 광물들의 순서를 나타내는 문자열 배열 minerals가 매개변수로 주어질 때, 마인이 작업을 끝내기까지 필요한 최소한의 피로도를 return 하는 solution 함수를 완성해주세요.

---

알고리즘

-곡괭이 최대 범위까지 광물을 자름

광물을 우선순위대로 튜닝함

내가정한 우선순위

1.다이아 개수가 많은 그룹 우선

2.다이아 개수가 같으면 철 개수가 많은 그룹 우선

3.다이아와 철 개수가 모두 같으면 전체 광물 개수가 많은 그룹 우선

우선순위대로 배열을 돌면서 곡괭이 하나씩 소모

곡괭이에 맞게 피로도 정답에 더하기

---

코드

 public static int solution(int[] picks, String[] minerals) {

        int answer = 0;

        int pm = 0;

        int[] op = picks.clone();

        for (int i = 0; i < picks.length; i++) {

            pm += picks[i] * 5;

            picks[i] *= 5;

        }

        Map<Integer, Map<String, Integer>> mgroups = new LinkedHashMap<>();

        String[] mineralNames = { "diamond", "iron", "stone" };

        int limit = Math.min(minerals.length, pm);

        for (int i = 0; i < limit; i += 5) {

            int groupIndex = i / 5;

            Map<String, Integer> counts = new LinkedHashMap<>();

            for (String mineral : mineralNames) {

                counts.put(mineral, 0);

            }

            for (int j = i; j < Math.min(i + 5, limit); j++) {

                counts.merge(minerals[j], 1, Integer::sum);

            }

            mgroups.put(groupIndex, counts);

        }

        mgroups.forEach((key, value) -> System.out.println(key + "=" + value));

        System.out.println("-------------------------");

        List<Map.Entry<Integer, Map<String, Integer>>> sortedGroups = new ArrayList<>(mgroups.entrySet());

        for (int i = 0; i < sortedGroups.size(); i++) {

            for (int j = i + 1; j < sortedGroups.size(); j++) {

                Map<String, Integer> a = sortedGroups.get(i).getValue();

                Map<String, Integer> b = sortedGroups.get(j).getValue();

                int aSize = a.get("diamond") + a.get("iron") + a.get("stone");

                int bSize = b.get("diamond") + b.get("iron") + b.get("stone");

                boolean swap = false;

                if (a.get("diamond") < b.get("diamond")) {

                    swap = true;

                } else if (a.get("diamond").equals(b.get("diamond"))) {

                    if (a.get("iron") < b.get("iron")) {

                        swap = true;

                    } else if (a.get("iron").equals(b.get("iron"))) {

                        if (aSize < bSize) {

                            swap = true;

                        }

                    }

                }

                if (swap) {

                    Map.Entry<Integer, Map<String, Integer>> temp = sortedGroups.get(i);

                    sortedGroups.set(i, sortedGroups.get(j));

                    sortedGroups.set(j, temp);

                }

            }

        }

        sortedGroups.forEach(System.out::println);

        System.out.println("--------------------------");

        System.out.println("시작곡괭이: " + Arrays.toString(picks));

        for (int ii = 0; ii < sortedGroups.size(); ii++) {

            Map.Entry<Integer, Map<String, Integer>> mineralss = sortedGroups.get(ii);

            Map<String, Integer> mineral = mineralss.getValue();

            System.out.println("타겟 그룹: " + mineralss);

            for (int i = 0; i < op.length; i++) {

                System.out.println("곡괭이 종류: " + i + ", 보유 개수: " + op[i]);

                if (op[i] <= 0) {

                    System.out.println(i + "번 곡괭이 없음");

                    continue;

                }

                for (Map.Entry<String, Integer> entry : mineral.entrySet()) {

                    String name = entry.getKey();

                    int count = entry.getValue();

                    if (count == 0) {

                        continue;

                    }

                    System.out.println("타겟 광물: " + name + ", " + count);

                    int mined = count ;

                    if (i == 0) {

                        answer += mined;

                    } else if (i == 1) {

                        if (name.equals("diamond")) {

                            answer += mined * 5;

                        } else {

                            answer += mined;

                        }

                    } else if (i == 2) {

                        if (name.equals("diamond")) {

                            answer += mined * 25;

                        } else if (name.equals("iron")) {

                            answer += mined * 5;

                        } else {

                            answer += mined;

                        }

                    }

 

                   

                }

                op[i]=op[i]-1;

                break;

            }

        }

        System.out.println("--------------------------");

        System.out.println(sortedGroups);

        System.out.println("도끼사용완료: " + Arrays.toString(picks));

        System.out.println(answer);

        return answer;

    }

 

---

결과

---

gpt피드백

-개선 우선순위는 1번 정렬 교체 → 2번 원본 배열 변경 제거 → 3·4번 코드 간소화야.

특히 3번과 4번은 알고리즘을 바꾸는 게 아니라 코드를 간결하게 만드는 선택 사항이야

현재 직접 작성한 이중 반복문 정렬:

 

for (int i = 0; i < sortedGroups.size(); i++) {
    for (int j = i + 1; j < sortedGroups.size(); j++) {
        // 비교 및 교환
    }
}

 

이 부분을 sort()로 바꾸면 돼.

 

sortedGroups.sort((a, b) -> {
    Map<String, Integer> x = a.getValue();
    Map<String, Integer> y = b.getValue();

    int diamond = Integer.compare(
        y.get("diamond"), x.get("diamond")
    );

    if (diamond != 0) return diamond;

    return Integer.compare(
        y.get("iron"), x.get("iron")
    );
});
이제 picks[i] *= 5는 필요 없어. 원본 배열을 변경하지 않는다는 장점도 있어

 

 

 

---

배운점느낀점

-와 내가 이문제를 풀수있어서 다행이다

중간에 몇번 포기해야하나 싶었다

생각을 코드로 옮기는데 너무 복잡헀다

일단 문제에 곡괭이를 한번들면 끝까지 써야한다 1개를

그러면 1개는 5개의 광물을 캔다 이걸 보고 생각이났다

아 그러면 곡괭이1개가 5개인거나 마찬가지네? 하고 

그러면 광물을 5개씩 잘라야겠다 하고 

그리고 나서 다시 사람 처럼 생각했다

나라면 곡괭이를 배분할때 가장 효율적이게 할테니

가장 비싼 순으로 5개씩나눈 2차원 광물 배열을 정렬해야겠다

이생각이들었다 그리고 이제 곡괭이를 소모하면 되겠다 싶었다 

근데 곡괭이 개수 컨트롤부분에서 심하게 헤맸다

난 그냥 어차피 곡괭이 1개당 광물 최대 5개로 하니까 곡괭이 배열자체를 개수*5로 바꿔어서 했다

그랬더니 내가 간과 했던 일이있었다 

int[] picks = {0, 1, 1};

 

String[] minerals = {

    "iron", "iron", "iron", "iron", "iron",

    "diamond"

};

곡괭이를 낱개로 바꾼다움 -1씩 하니 저 예제에서 잘못된답이나왔다

순설르 바꿔서 채굴이 되는 현상이 일어난것이다 

멘붕이 왔다 코드를 다지우고 다시 천천히 생각했다 

그때 번뜩 아 배열하나가 어차피 곡괭이 하나구나!하고

즉 곡괭이를 낱게로 해서 마이너스하면 안돼고 

세트로 마이너스가일어나야했었다 

그래서 다시 곡괭이 마이너스로직을 바꿨다

그리고 통과했다 힘들었다.