자바 - 프로그래머스 / 광물 캐기

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

프로그래머스

LV 2

 

구현 방법

핵심 : diamond, iron, stone 갯수 많은 순서로 좋은 곡괭이 쓰면 최소의 피로도를 얻을 수 있다.

1. (곡괭이 수) * 5와 minerals.length 중 작은 값을 iterSize에 저장한다

   =>  "광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캡니다." 이 조건 때문에 해야함. 

          이거 안하면 test case 8번 오류 뜬다...

//test case 8, 정답 : 14
int[] picks = {1, 1, 0};
String[] minerals = {"diamond", "diamond", "diamond", "iron", "iron", 
        			"diamond", "iron", "stone","iron", "iron", "diamond","diamond"};

2.  iterSize 만큼 minerals 5개씩 묶기(5개는 해시맵으로 저장 후 => list에 넣기)

3. list를 diamond, iron, stone 개수 순서로 내림차순 정렬하기

4. 곡괭이 피로도 계산하기

코드

import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Arrays;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        
       List<HashMap<String, Integer>> group = new ArrayList<>();
        HashMap<String, Integer> temp = new HashMap<>();
        temp.put("diamond", 0);
        temp.put("iron", 0);
        temp.put("stone", 0);

        int picksSum = Arrays.stream(picks).sum() * 5;

        int iterSize = 0;

        if (picksSum > minerals.length)
            iterSize = minerals.length;
        else {
            iterSize = picksSum;
        }

        //mineral 5개씩 묶기
        for(int i = 0; i < iterSize; i++) {
            temp.put(minerals[i], temp.get(minerals[i]) + 1);
            if ((i + 1) % 5 == 0) {
                group.add(temp);
                temp = new HashMap<String, Integer>();
                temp.put("diamond", 0);
                temp.put("iron", 0);
                temp.put("stone", 0);
            }
            if (i == minerals.length - 1) {
                group.add(temp);
            }
        }

        // diamond, iron, stone 갯수 많은 순으로 정렬
        Collections.sort(group, (o1, o2) ->{
            if(o2.get("diamond")!= o1.get("diamond")) {
                return o2.get("diamond") - o1.get("diamond");
            } else {
                if(o2.get("iron") != o1.get("iron")) {
                    return o2.get("iron") - o1.get("iron");
                } else {
                    return o2.get("stone") - o1.get("stone");
                }
            }
        });

        int curIndex = 0;
        for(int i = 0; i < picks.length; i++) {
            while (picks[i] > 0) {
                if (curIndex == group.size())
                    break;

                if (i == 0) {
                    //diamond 곡괭이
                    answer += group.get(curIndex).get("diamond")
                            + group.get(curIndex).get("iron")
                            + group.get(curIndex).get("stone");
                } else if (i == 1) {
                    //iron 곡괭이
                    answer += group.get(curIndex).get("diamond") * 5
                            + group.get(curIndex).get("iron")
                            + group.get(curIndex).get("stone");
                } else {
                    //stone 곡괭이
                    answer += group.get(curIndex).get("diamond") * 25
                            + group.get(curIndex).get("iron") * 5
                            + group.get(curIndex).get("stone");
                }
                picks[i]--;
                curIndex++;
            }
            if (curIndex == group.size())
                break;
        }
        
         
        return answer;
    }
}

 

느낀 점

testcase 실패 원인은 조건 잘 읽어보면 해결 된다.

리스트 정렬 하기 싫으면 우선순위 큐 쓰면 될거 같다.

bfs 방식으로 접근 해 보자.