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

문제를 읽고 입력값이 크지 않아 완전탐색을 생각했었다.

백트래킹을 이용하면 어찌어찌 구현할 수 있겠다고 생각했지만, 그리 끌리지는 않았다.

주어진 순서대로 탐색을 해야 하고 가중치가 있기 때문에 그리디로 해결할 수 있다고 생각하여

도전한 결과 풀이에 성공했다.

---

로직

곡괭이가 없거나, 더 캘 광물이 없다면 종료해야 하므로 매 순회마다 종료 조건을 설정했다.

하나의 곡괭이는 5번을 사용할 수 있으므로 미네랄 배열을 5개씩 그룹을 만들어 탐색한다.

하나의 그룹을 각각 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이로 채굴했을 때의 피로도를 객체로 만들어 list에 넣는다.

list안의 객체를 돌 곡괭이를 사용했을 때의 피로도를 기준으로 내림차순 정렬하고

가장먼저 다이아몬드 곡괭이부터 사용하고, 철 곡괭이를, 돌 곡괭이 순으로 곡괭이를 사용하여 answer를 구하면 된다.

 

최종 코드

import java.util.*;

class Solution {
    public int solution(int[] picks, String[] minerals) {
		int answer = 0;

		int[][] arr = new int[][]{{1, 1, 1}, {5, 1, 1}, {25, 5, 1}};
		int size = Arrays.stream(picks).sum();
		List<Mineral> list = new ArrayList<>();

		for(int i = 0; i < minerals.length; i+=5) {
			if(size == 0) {
				break;
			}

			int diamond = 0;
			int iron = 0;
			int stone = 0;

			for(int j = i; j < i + 5; j++) {
				if(j == minerals.length) {
					break;
				}

				int mineral = 0;
				if(minerals[j].startsWith("i")) {
					mineral = 1;
				} else if(minerals[j].startsWith("s")) {
					mineral = 2;
				}

				diamond += arr[0][mineral];
				iron += arr[1][mineral];
				stone += arr[2][mineral];
			}
			list.add(new Mineral(diamond, iron, stone));
			size--;
		}

		list.sort(((o1, o2) -> (o2.stone - o1.stone)));
        
        for(Mineral m : list) {
			int diamond = m.diamond;
			int iron = m.iron;
			int stone = m.stone;

			if(picks[0] > 0) {
				answer += diamond;
				picks[0]--;
				continue;
			}

			if(picks[1] > 0) {
				answer += iron;
				picks[1]--;
				continue;
			}

			if(picks[2] > 0) {
				answer += stone;
				picks[2]--;
			}
		}
        
		return answer;
	}

	class Mineral {
		private int diamond;
		private int iron;
		private int stone;

		public Mineral(int diamond, int iron, int stone) {
			this.diamond = diamond;
			this.iron = iron;
			this.stone = stone;
		}
	}
}