[PRG] 172927 광물 캐기 JAVA

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

프로그래머스

 
메모리: 80 MB
시간: 3.63 ms
 

문제분석

완전탐색

그리디, DP, 완전탐색 중 고민하다가
그리디는 한 차례 실패하고 DFS로 풀이 방법을 바꿔보았다 !

광물의 순서를 바꿀 수 없기 때문에 그리디로는 우선순위를 매핑하기 쉽지 않을 것 같았다.
그래서 모든 경우를 따져보기 위해 DFS 선택 !

 

걸리 시간

50분 ⏱️

 

풀이 방법

1. dfs를 위해 매개변수, 곡괭이 카운트 담을 배열, 우선순위 map, 출력값 등을 전역변수로 설정
2. 중요도 map에 저장 (※ 다이아 : 0, 철 : 1, 돌 : 2)
3. 곡괭이 수에 따라 캘 수 있는 광물 수 배열에 저장 (picks[] * 5)
4. dfs 연산
	4-1. return - 더이상 캘 수 있는 광물이 없을 경우 (피로도 최소값 저장)
	4-2. 모든 곡괭이 사용해보기
	4-3. 해당 곡괭이로 5개의 광물 캐기
	4-4. 피로도 계산 (포인트에 따로 정리해 놓겠습니다 !)



※ 중요도를 저렇게 설정한 이유는 입력으로 주어지는 picks 배열의 인덱스와 맞춰주기 위함 (나중에 계산에 쓰기 위해)

 

포인트

<피로도 계산>

[광석 (map)]
다이아 : 0
철 : 1
돌 : 2


[곡괭이 (배열)]
다이아 : 0
철 : 1
돌 : 2


[배열 - map]
0 - 0 : 1  (5^0)
0 - 1 : 1  (5^ -1)
0 - 2 : 1  (5^ -2)

1 - 0 : 5  (5^1)
1 - 1 : 1  (5^ 0)
1 - 2 : 1  (5^ -1)

2 - 0 : 25 (5^2)
2 - 1 : 5  (5^1)
2 - 2 : 0  (5^0)

※ 즉, 차이가 음수일 경우 0으로 바꿔주면
피로도를 5의 제곱으로 간단히 계산 가능

 

코드

import java.util.*;

class Solution {
    public int[] cnt;        // 곡괭이 별로 캘 수 있는 광석 수
    public String[] str;     // 매개변수로 입력받은 minerals
    public int answer = Integer.MAX_VALUE;   // 출력값
    public Map<String, Integer> map;  // 간단한 피로도 계산을 위해 중요도 저장

    public int solution(int[] picks, String[] minerals) {
        // 중요도 저장
        map = new HashMap<>();
        map.put("diamond", 0);
        map.put("iron", 1);
        map.put("stone", 2);

        // 곡괭이 수에 따라 캘 수 있는 광석 수 저장
        cnt = new int[3];
        for(int i = 0; i < 3; i ++) {
            cnt[i] = picks[i] * 5;
        }

        // minerals 전역변수에 저장
        str = new String[minerals.length];
        str = Arrays.copyOf(minerals, minerals.length);

        // dfs 연산
        dfs(0, 0);

        return answer;
    }

    public void dfs(int idx, int sum) {
        // 더 이상 캘 광석이 없으면 피로도 최솟값 저장 후 return
        if(idx >= str.length || cnt[0] + cnt[1] + cnt[2] == 0) {
            answer = Math.min(answer, sum);
            return;
        }

        int tired = 0;      // 피로도 저장
        int index = idx;    // 인덱스 저장

        // 모둔 곡괭이 사용해보기
        outer : for(int i = 0; i < 3; i ++) {
            // 광물을 캘 수 없는 곡괭이는 continue
            if(cnt[i] <= 0) continue;
            int prev = cnt[i];  // 카운트 되돌리기 위해 저장
            // 5개 광물 캐기
            for(int j = index; j < idx + 5; j ++) {
                if(j >= str.length) break;
                if(cnt[i] <= 0) continue outer;
                int calc = i - map.get(str[j]);
                if(i - map.get(str[j]) < 0) calc = 0;
                tired += Math.pow(5, calc);
                cnt[i] --;
            }

            dfs(idx + 5, sum + tired);
            // 변수 초기화
            tired = 0;
            index = idx;
            cnt[i] = prev;
        }
    }
}