99클럽 코테 스터디 39일차 TIL - [프로그래머스] 광물 캐기 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 광물 캐기 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/172927

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 송전탑의 개수 n, 전선 정보가 담긴 정수 2차원 배열 wires
출력 : 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)

가능한 시간복잡도

O(n^2)

알고리즘 선택

그리디

📌 코드 설계하기

1. 인접 리스트를 이용해 그래프를 생성하고, 간접 정보를 인접 리스트에 추가한다.
2. 간선을 하나씩 제거하면서 그래프가 두 부분으로 나뉘었을 때의 노드 수를 계산한다.
3. BFS를 사용해 한쪽 서브트리의 노드 수를 계산한다.
4. 두 서브트리의 노드 수 차이를 계산하고, 최소값을 업데이트한다.
5. 다음 계산을 위해 제거했던 간선을 다시 복구한다.
6. 모든 간선에 대해 위의 작업을 반복한 후, 가장 작은 크기 차이를 반환한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

어떻게 해결했는지

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        int totalPicks = picks[0] + picks[1] + picks[2];  // 전체 곡괭이 개수
        int size = Math.min((minerals.length + 4) / 5, totalPicks); // 광물의 그룹 수 (5개씩 자르기 때문에 길이를 5로 나눈 값)

        // 그룹화하여 피로도를 저장하는 배열
        int[][] fatigue = new int[size][3];

        // 광물을 5개씩 그룹화
        for (int i = 0; i < size * 5 && i < minerals.length; i++) {
            int group = i / 5;  // 현재 그룹
            String mineral = minerals[i];
            
            // 다이아 곡괭이 피로도
            if (mineral.equals("diamond")) {
                fatigue[group][0] += 1;  // 다이아몬드 곡괭이는 다이아몬드를 캐는 데 피로도가 1
                fatigue[group][1] += 5;  // 철 곡괭이는 다이아몬드를 캐는 데 피로도가 5
                fatigue[group][2] += 25; // 돌 곡괭이는 다이아몬드를 캐는 데 피로도가 25
            } else if (mineral.equals("iron")) {
                fatigue[group][0] += 1;  // 다이아몬드 곡괭이는 철을 캐는 데 피로도가 1
                fatigue[group][1] += 1;  // 철 곡괭이는 철을 캐는 데 피로도가 1
                fatigue[group][2] += 5;  // 돌 곡괭이는 철을 캐는 데 피로도가 5
            } else if (mineral.equals("stone")) {
                fatigue[group][0] += 1;  // 다이아몬드 곡괭이는 돌을 캐는 데 피로도가 1
                fatigue[group][1] += 1;  // 철 곡괭이는 돌을 캐는 데 피로도가 1
                fatigue[group][2] += 1;  // 돌 곡괭이는 돌을 캐는 데 피로도가 1
            }
        }

        // 피로도를 기준으로 내림차순 정렬
        Arrays.sort(fatigue, (a, b) -> b[2] - a[2]);

        // 최소 피로도 계산
        for (int i = 0; i < size; i++) {
            if (picks[0] > 0) { // 다이아몬드 곡괭이가 남아있을 경우
                answer += fatigue[i][0];
                picks[0]--;
            } else if (picks[1] > 0) { // 철 곡괭이가 남아있을 경우
                answer += fatigue[i][1];
                picks[1]--;
            } else if (picks[2] > 0) { // 돌 곡괭이가 남아있을 경우
                answer += fatigue[i][2];
                picks[2]--;
            }
        }

        return answer;
    }
}