평가
결과 : 성공
풀이시간 : 44분
구현 + 그리디 문제. 마냥 그리디라고 보기에는 구현시 고려할 부분들이 많다.
아이디어
- 자원은 무조건 순서대로 채굴해야 합니다.
- 하나의 곡괭이로는 5개의 자원을 채굴할 수 있습니다.
가장 중요한 건 이 문제가 그리디라는 걸 파악하는 것입니다.
바로 이 문제에서는 비싼 곡괭이는 항상 비싼 자원이 많은 곳을 팔 때 사용해야 전체 피로도가 가장 낮게 나온다 는 사실을 깨달아야 합니다.
말이 참 어려우니 예시를 통해 설명드리겠습니다.
["iron", "iron", "iron", "iron", "iron", "diamond","stone"] 이렇게 자원이 주어졌다고 가정하겠습니다.
하나의 곡괭이로는 5개씩 자원을 채굴할 수 있으니 아래와 같은 2개의 Group을 만들 수 있습니다.
["iron", "iron", "iron", "iron", "iron"]
["diamond"]
다이아 곡괭이, 철 곡괭이가 한 개씩 있다면 어떻게 사용해야 피로도를 최소로 만들 수 있을까요?
정답을 말씀드리면 철이 5개 있는 Group에 철 곡괭이, 다이아가 1개 있는 Group에 다이아 곡괭이를 써야 합니다.
위 방식으로 하면 5 + 1, 6의 피로도를 사용합니다.
반대로 사용하면 5 + 5, 10의 피로도를 사용하기 때문에 위 방식이 더 효과적입니다.
어떻게 곡괭이를 사용해야 효과적으로 피로도를 낮출 수 있을까요?
이 표를 주의깊게 살펴볼 필요가 있습니다.
비싼 광물은 성능이 좋지 않은 곡괭이로 채굴할 때 피로도가 엄청나게 올라갑니다.
위 표를 보시면 철 곡괭이는 다이아 1개를 채굴할 때와 철 5개를 채굴할 때 피로가 같습니다.
철 곡괭이 2개가 있는 상황이라고 가정하겠습니다.
[다이아] 를 채굴하면 5의 피로를 얻고, [철,철,철,철,철]을 채굴하면 5의 피로를 얻습니다.
만약에 철 곡괭이 한개가 다이아 곡괭이로 바뀐다면 다이아 곡괭이로 어떤 걸 파야 할까요?
다이아를 빼고 다른 자원들은 다이아 곡괭이나 철 곡괭이나 동일한 피로도를 갖습니다.
그러니까 다이아를 대신 파주는게 좋겠죠?
다이아가 딱 한 개 있다면, 가장 피로도가 조금 드는 상황은 [다이아] 가 있는 상황입니다.
다이아가 한 개도 없을 때, 가장 파기 힘든 경우는 [철,철,철,철,철] 입니다.
철 곡괭이 입장에서는 다이아몬드 0개짜리 Group을 파는 어떤 상황에서도 다이아몬드 1개를 파는 피로도보다 작거나 같습니다.
ex. 철 5개(피로도 5), 돌 5개(피로도 5), 철 3개(피로도3) ,...
즉, 다이아 곡괭이가 있다면 다른 조건은 볼 필요도 없이 다이아 자원이 많은 곳에 쓰는게 효과적이라는 의미입니다.
마찬가지로 철 곡괭이는 돌 곡괭이에 비해 다이아몬드를 팔 때 가장 효율이 좋습니다. 다이아만큼은 아니지만 철을 팔 때도 효율이 좋습니다.
그래서 Group을 만들어주고 다음과 같은 우선순위를 통해 정렬합니다.
groups.sort(new Comparator<>() {
@Override
public int compare(Group o1, Group o2) {
// 다이아 개수 비교. 다이아 개수가 많은 게 우선순위가 높다
if (o1.diamond != o2.diamond) {
return o2.diamond - o1.diamond;
}
// 다이아 개수가 같다면 철 개수 비교
if (o1.iron != o2.iron) {
return o2.iron - o1.iron;
}
// 철 개수도 같다면 돌 개수 비교
return o2.stone - o1.stone;
}
});
곡괭이 역시 비싼 곡괭이들부터 순서대로 사용해서 각각의 Group을 채굴하면 되는 문제였습니다~~
정답 코드
import java.util.*;
class Solution {
public int solution(int[] picks, String[] minerals) {
// tools: 비싼 곡괭이부터 차근차근 들어간다
List<Integer> tools = new ArrayList<>();
int toolNum = 0;
for(int cnt: picks) {
for(int i=0; i<cnt;i++) {
tools.add(toolNum);
}
toolNum++;
}
// groups에 각 묶음들을 넣는다
// 묶음은 5개를 기준으로 하고, 해당 묶음에 존재하는 자원들을 기록한다
List<Group> groups = new ArrayList<>();
int groupCnt = (minerals.length + 4)/ 5;
for(int i=0; i< groupCnt; i++) {
// 곡괭이 개수만큼만 Group을 채굴할 수 있다
if (i >= tools.size()) {
break;
}
Group group = new Group();
for(int j=i*5; j<i*5 + 5; j++) {
if (minerals.length <= j) {
break;
}
if (minerals[j].equals("diamond")) {
group.diamond++;
} else if (minerals[j].equals("iron")) {
group.iron++;
} else {
group.stone++;
}
}
groups.add(group);
}
// groups을 정렬한다. 다이아 많은거 -> 철 많은거 -> 돌 많은거 기준으로
groups.sort(new Comparator<>() {
@Override
public int compare(Group o1, Group o2) {
// 다이아 비교
if (o1.diamond != o2.diamond) {
return o2.diamond - o1.diamond;
}
// 철비교
if (o1.iron != o2.iron) {
return o2.iron - o1.iron;
}
return o2.stone - o1.stone;
}
});
int idx = 0;
int total = 0;
for(Group group : groups) {
if (idx >= groups.size()) {
// 곡괭이 다 씀
break;
}
int tool = tools.get(idx++);
total += group.worked(tool);
}
return total;
}
static class Group {
int diamond = 0;
int iron = 0;
int stone = 0;
public int worked(int tool) {
if (tool == 0) {
return diamond + iron + stone;
}
if (tool == 1) {
return diamond * 5 + iron + stone;
}
return diamond * 25 + iron * 5 + stone;
}
}
}