[Algorithm] Programmers_광물캐기 in Java

💡 Programmers Lv2. 광물캐기:

주어진 곡괭이를 통해 광물을 가장 효율적으로 파기

🌱 코드 in Java

알고리즘: greedy

import java.util.*;

class Solution {
    static class Tired {
        int dia;
        int iron;
        int stone;
        
        public Tired(int dia, int iron, int stone) {
            this.dia = dia;
            this.iron = iron;
            this.stone = stone;
        }
    }

    public int solution(int[] picks, String[] minerals) {
        int totalPicks = Arrays.stream(picks).sum();
        int answer = 0;
        List<Tired> tireds = new ArrayList<>();
        int len = minerals.length;
        int i = 0;
        while (i < len && totalPicks > 0) {
            int j = i, dia = 0, iron = 0, stone = 0;
            while (j < len && j < i + 5) {
                String m = minerals[j++];
                dia += 1;
                if (m.equals("diamond")) {
                    iron += 5;
                    stone += 25;
                } else {
                    iron += 1;
                    stone = m.equals("iron") ? stone + 5 : stone + 1;
                }
            }
            i += 5;
            totalPicks--;
            tireds.add(new Tired(dia, iron, stone));
        }
        Collections.sort(tireds, ((o1, o2) -> o2.stone - o1.stone));
        for (Tired t : tireds) {
            if (picks[0] > 0) {
                answer += t.dia;
                picks[0]--;
            } else if (picks[1] > 0) {
                answer += t.iron;
                picks[1]--;
            } else {
                answer += t.stone;
            }
        }
        return answer;
    }
}

이번 문제는 한 곡괭이로 연속해서 최대 5회 캘 수 있고, 피로도가 가장 적게 드는 방향으로 곡괭이를 사용하도록 하는 문제였다. 돌 곡괭이 사용 시 피로도 가중치가 가장 높기 때문에 각 곡괭이별 피로도를 구한 후 돌 곡괭이 피로도를 내림차순 기준으로 정렬해서, 해당 구간을 상위 곡괭이로 해결해 나가는 것이 중요한 문제였다.

여기서 중요한 점은 한 곡괭이를 선택했으면 연속 5회 사용해야 한다는 것과 광물 || 곡괭이 여유분을 동시에 고려해야 한다는 것이다.
광물을 다 캐지 못했더라도 곡괭이를 다 썼을 경우 계산하지 않아야 하며, 곡괭이가 남았더라도 있는 광물만큼만 계산해야 하는 것이다.

알고리즘 문제를 java로 풀어보긴 처음인데, 내가 진짜 인텔리제이없이는..
아니 그냥 Java 알못임을 너무 여실히 깨달아버렸다..

제일 어려웠던 점은 대체 sorting을 어떻게 해야하는지.. compare 함수 오버라이딩에 대해서 분명히 옛날에 공부를 했는데..

이번에 여실히 느꼈다. 말만 하지말고 자바 람다와 스트림을 공부해야겠다.
그외의 것들도 다...

🧠 기억하자

1. Collentions.sort를 통해 sorting을 진행할 수 있다.

• 현재처럼 객체를 만들어 사용할 수도 있고, 2차원 배열을 만든 후 인덱스 기준으로도 sorting해 줄 수 있다.

2. Arrays.stream.sum()

• 합계를 구할 수 있다.

3. length() vs length

• lenghth()는 문자열에, length는 배열에

4. charAt(index)