https://school.programmers.co.kr/learn/courses/30/lessons/172927
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
📌- 풀이
처음은 완전탐색을 하면 되지 않을까 생각해서 완전 탐색으로 문제를 풀다가 아니다 싶어서 다른 방법을 찾아봄
핵심적인 풀이법은
- 광물을 5개씩 집단을 만들어서 각자 다이아, 철, 돌로 캤을 때의 값들을 만듬
- 1번에서 나온 값들로 집단 마다 객체를 만들어서 list에 삽입
이렇게 만들면
ex) list에 Mineral 객체 => (30, 50, 80) 이렇게 list에 쌓이게 됨 - 가장 중요한 부분은 최솟값을 구하는 문제이므로 각 집단에서 돌을 기준으로 내림차순 정렬을 함
돌로 내림차순 정렬을 하는 이유는
예를 들어서 두 개의 집단이 있을 때 돌로 캤을 때의 비용이 각각 180, 100이라면
180이 나온 집단을 다이아 곡괭이나 철 곡괭이로 캤을 때, 비용이 더 절감되기 때문
- 정렬된 집단을 기준으로 다이아 곡괭이부터 하나씩 써가면서 곡괭이를 다 쓸때까지 결과값에 더하면 최솟값이 나옴
여기서 어려웠던 부분은 처음 정렬할 기준을 찾는 것이 어려웠음
🚨 - 주의할 점
처음 문제를 풀고 제출을 했을 때 계속 테스트케이스 1개가 틀려서 뭔지 찾아봤는데,
예를 들자면
곡괭이가 2개이고, 집단의 수가 3개 이상일 경우
-> 3개의 집단을 정렬하는 것이 아니라, 마지막 집단을 버리고 앞의 2개의 집단을 정렬해서 계산해야 함
여기서 list를 슬라이싱해서 정렬을 해줘야 한다.
이런 예외케이스가 있어서 이 부분에서도 시간을 많이 썼다.
🔥 - Java 코드
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}};
List<Mineral> list = new ArrayList<>();
int total_number = 0;
for(int m : picks){ // 광물 집합의 개수 보다 곡괭이의 개수가 적을 때를 위해 total_number 만듬
total_number += m;
}
for(int i=0;i<(minerals.length/5) + 1 ;i++){
int dia = 0;
int iron = 0;
int stone = 0;
for(int j=i*5;j<(i*5)+5 && j<minerals.length;j++){
int num =0;
switch(minerals[j].charAt(0)){
case 'd':
dia += arr[0][num];
iron += arr[1][num];
stone += arr[2][num];
break;
case 'i':
num=1;
dia += arr[0][num];
iron += arr[1][num];
stone += arr[2][num];
break;
case 's':
num=2;
dia += arr[0][num];
iron += arr[1][num];
stone += arr[2][num];
break;
}
}
list.add(new Mineral(dia,iron,stone));
}
if(total_number < list.size()){ // 곡괭이가 집단의 수보다 적을 때 예외처리, 슬라이싱
list = list.subList(0,total_number);
}
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;
}
}
}