Level 2: 광물 캐기, 그리디 알고리즘

참고 문서

• Programmers: 광물 캐기

이 문서의 내용

Step 1: 피로도 계산

어떤 곡갱이를 사용해 광물을 캘 때는 미리 정해진 피로도를 소모합니다.

피로도는 이차원 배열로 미리 구성하면 인덱스를 사용하여 쉽게 접근 할 수 있습니다.

int[][] stamina = new int[][] {{1, 1, 1 }, { 5, 1, 1 }, { 25, 5, 1 }};
List<String> staminaIdx = Arrays.stream(new String[] { "diamond", "iron", "stone" }).toList();

예를 들어 인자 minerals가 { "iron", "diamond", "iron" }인 경우 첫 번째 요소인 iron을 캐낼 때 곡갱이 별로 소모되는 피로도는 다음처럼 구할 수 있습니다.

int staminaIdxOf = staminaIdx.indexOf(minerals[0]);
for (int i = 0; i < 3; ++i) 
{
	int v = stamina[i][staminaIdxOf];
}

Step 2-1: 광물을 Fragment로 구성

어떤 곡갱이를 선택하더라도 연속되는 광물 5개는 반드시 동일한 곡갱이로 캐내야 합니다.

광물 5개는 하나의 조각(Fragment)로 구성 할 수 있으며 Fragment는 3개의 곡갱이로 캐낼 때의 피로도 미리 계산 할 수 있습니다.

List<Integer[]> fragments = new ArrayList<>();
for (int i = 0; i < minerals.length; ++i) 
{
	int fragmentId = i / 5;
	if (fragmentId >= fragments.size())
		fragments.add(new Integer[] { 0, 0, 0 });
	int staminaIdxOf = staminaIdx.indexOf(minerals[i]);
	for (int j = 0; j < 3; ++j) {
		fragments.get(fragmentId)[j] += stamina[j][staminaIdxOf];
	}
}

문제에서 제시하는 입력#1은 두 개의 Fragment로 구성됩니다.

Step 2-2: Fragment 구성의 예외적인 중단

인자 picks는 곡갱이 3종류의 수량을 표현합니다. 곡갱이 1개는 광물을 5개 캐낼 수 있으며 더 이상 남아있는 곡갱이가 없으면 Fragment 구성도 중단합니다.

Step 2-1의 Fragment 구성 코드의 반복문에서 잔여 곡갱이 개수를 검사합니다.

int remainPicks = Arrays.stream(picks).sum() * 5;
for (int i = 0; i < minerals.length && 0 < remainPicks; ++i, --remainPicks) 
{
	int fragmentId = i / 5;
    ...
}

Step 3: 그리드 알고리즘을 사용하여 최적의 수 계산

이 문제를 푸는 방법은 크게 두 가지입니다.

• 모든 곡갱이 조합을 사용하는 완전 탐색 풀이
• 그리드 알고리즘을 사용하여 풀이

완전 탐색을 사용하게 되면 로직도 복잡해지고 가장 큰 문제는 시간 초과 오류가 발생합니다.

다음 코드에서는 그리드 알고리즘을 사용해서 문제를 해결합니다.

import java.util.*;

class Solution {
	public int solution(int[] picks, String[] minerals)
	{
		int[][] stamina = new int[][] {{1, 1, 1 }, { 5, 1, 1 }, { 25, 5, 1 }};
		List<String> staminaIdx = Arrays.stream(new String[] { "diamond", "iron", "stone" }).toList();
		
		List<Integer[]> fragments = new ArrayList<>();
		int remainPicks = Arrays.stream(picks).sum() * 5;
		for (int i = 0; i < minerals.length && 0 < remainPicks; ++i, --remainPicks) 
		{
			int fragmentId = i / 5;
			if (fragmentId >= fragments.size())
				fragments.add(new Integer[] { 0, 0, 0 });
			int staminaIdxOf = staminaIdx.indexOf(minerals[i]);
			for (int j = 0; j < 3; ++j) {
				fragments.get(fragmentId)[j] += stamina[j][staminaIdxOf];
			}
		}
		
		Collections.sort(fragments, (lp, rp) -> {
			return rp[2] - lp[2];
		});
		
		int answer = 0;
		for (Integer[] o : fragments)
		{
			for (int i = 0; i < picks.length; ++i) {
				if (0 < picks[i]) {
					answer += o[i];
					--picks[i];
					break;
				}
			}
		}
		
		return answer;
	}
}

코드		비고
Line 22:24	Collections.sort()	Fragment를 피로도가 높은 순서로 내림차순 정렬합니다. 이때 편차가 가장 큰 stone 곡갱이를 사용한 경우로 계산합니다.
Line 27:36	for (int i = 0; i < picks.length; ++i) { }	Fragment를 하나 처리 할 때 diamond 곡갱이부터 사용합니다. 만약 잔여 곡갱이가 없으면 다음 유형의 곡갱이를 사용합니다.

피로도가 높은 Fragment 순서대로 최적의 곡갱이를 선택하는 것이 중요합니다.