광물 캐기 - 프로그래머스 | Java

평가

결과 : 성공
풀이시간 : 44분

구현 + 그리디 문제. 마냥 그리디라고 보기에는 구현시 고려할 부분들이 많다.

아이디어

1. 자원은 무조건 순서대로 채굴해야 합니다.
2. 하나의 곡괭이로는 5개의 자원을 채굴할 수 있습니다.

가장 중요한 건 이 문제가 그리디라는 걸 파악하는 것입니다.
바로 이 문제에서는 비싼 곡괭이는 항상 비싼 자원이 많은 곳을 팔 때 사용해야 전체 피로도가 가장 낮게 나온다 는 사실을 깨달아야 합니다.
말이 참 어려우니 예시를 통해 설명드리겠습니다.

["iron", "iron", "iron", "iron", "iron", "diamond","stone"] 이렇게 자원이 주어졌다고 가정하겠습니다.
하나의 곡괭이로는 5개씩 자원을 채굴할 수 있으니 아래와 같은 2개의 Group을 만들 수 있습니다.

["iron", "iron", "iron", "iron", "iron"]
["diamond"]

다이아 곡괭이, 철 곡괭이가 한 개씩 있다면 어떻게 사용해야 피로도를 최소로 만들 수 있을까요?
정답을 말씀드리면 철이 5개 있는 Group에 철 곡괭이, 다이아가 1개 있는 Group에 다이아 곡괭이를 써야 합니다.
위 방식으로 하면 5 + 1, 6의 피로도를 사용합니다.
반대로 사용하면 5 + 5, 10의 피로도를 사용하기 때문에 위 방식이 더 효과적입니다.

어떻게 곡괭이를 사용해야 효과적으로 피로도를 낮출 수 있을까요?

이 표를 주의깊게 살펴볼 필요가 있습니다.
비싼 광물은 성능이 좋지 않은 곡괭이로 채굴할 때 피로도가 엄청나게 올라갑니다.
위 표를 보시면 철 곡괭이는 다이아 1개를 채굴할 때와 철 5개를 채굴할 때 피로가 같습니다.

철 곡괭이 2개가 있는 상황이라고 가정하겠습니다.
[다이아] 를 채굴하면 5의 피로를 얻고, [철,철,철,철,철]을 채굴하면 5의 피로를 얻습니다.
만약에 철 곡괭이 한개가 다이아 곡괭이로 바뀐다면 다이아 곡괭이로 어떤 걸 파야 할까요?
다이아를 빼고 다른 자원들은 다이아 곡괭이나 철 곡괭이나 동일한 피로도를 갖습니다.
그러니까 다이아를 대신 파주는게 좋겠죠?

다이아가 딱 한 개 있다면, 가장 피로도가 조금 드는 상황은 [다이아] 가 있는 상황입니다.
다이아가 한 개도 없을 때, 가장 파기 힘든 경우는 [철,철,철,철,철] 입니다.

철 곡괭이 입장에서는 다이아몬드 0개짜리 Group을 파는 어떤 상황에서도 다이아몬드 1개를 파는 피로도보다 작거나 같습니다.
ex. 철 5개(피로도 5), 돌 5개(피로도 5), 철 3개(피로도3) ,...

즉, 다이아 곡괭이가 있다면 다른 조건은 볼 필요도 없이 다이아 자원이 많은 곳에 쓰는게 효과적이라는 의미입니다.
마찬가지로 철 곡괭이는 돌 곡괭이에 비해 다이아몬드를 팔 때 가장 효율이 좋습니다. 다이아만큼은 아니지만 철을 팔 때도 효율이 좋습니다.

그래서 Group을 만들어주고 다음과 같은 우선순위를 통해 정렬합니다.

        groups.sort(new Comparator<>() {
            @Override
            public int compare(Group o1, Group o2) {
                // 다이아 개수 비교. 다이아 개수가 많은 게 우선순위가 높다
                if (o1.diamond != o2.diamond) {
                    return o2.diamond - o1.diamond;
                }
                // 다이아 개수가 같다면 철 개수 비교
                if (o1.iron != o2.iron) {
                    return o2.iron - o1.iron;
                }

				// 철 개수도 같다면 돌 개수 비교
                return o2.stone - o1.stone;
            }
        });
        

곡괭이 역시 비싼 곡괭이들부터 순서대로 사용해서 각각의 Group을 채굴하면 되는 문제였습니다~~

정답 코드

import java.util.*;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        
        // tools: 비싼 곡괭이부터 차근차근 들어간다
        List<Integer> tools = new ArrayList<>();
        
        int toolNum = 0;
        for(int cnt: picks) {
            for(int i=0; i<cnt;i++) {
                tools.add(toolNum);
            }
            toolNum++;
        }

        // groups에 각 묶음들을 넣는다
        // 묶음은 5개를 기준으로 하고, 해당 묶음에 존재하는 자원들을 기록한다
        List<Group> groups = new ArrayList<>();
        int groupCnt = (minerals.length + 4)/ 5;
        for(int i=0; i< groupCnt; i++) {

            // 곡괭이 개수만큼만 Group을 채굴할 수 있다
            if (i >= tools.size()) {
                break;
            }
            
            Group group = new Group();
            for(int j=i*5; j<i*5 + 5; j++) {
                if (minerals.length <= j) {
                    break;
                }
                if (minerals[j].equals("diamond")) {
                    group.diamond++;
                } else if (minerals[j].equals("iron")) {
                    group.iron++;
                } else {
                    group.stone++;
                }
            }
            groups.add(group);
        }
                
        // groups을 정렬한다. 다이아 많은거 -> 철 많은거 -> 돌 많은거 기준으로
        groups.sort(new Comparator<>() {
            @Override
            public int compare(Group o1, Group o2) {
                // 다이아 비교
                if (o1.diamond != o2.diamond) {
                    return o2.diamond - o1.diamond;
                }
                // 철비교
                if (o1.iron != o2.iron) {
                    return o2.iron - o1.iron;
                }
                return o2.stone - o1.stone;
            }
        });
        
        
        int idx = 0;
        int total = 0;
        for(Group group : groups) {
            if (idx >= groups.size()) {
                // 곡괭이 다 씀
                break;
            }
            int tool = tools.get(idx++);
            total += group.worked(tool);
        }
        
        return total;
    }
    
    static class Group {
        int diamond = 0;
        int iron = 0;
        int stone = 0;
        
        public int worked(int tool) {
            if (tool == 0) {
                return diamond + iron + stone;
            }
            if (tool == 1) {
                return diamond * 5 + iron + stone;
            }
            return diamond * 25 + iron * 5 + stone;
        }
    }
    
}