소요시간 : 1시간 40분
문제 풀이는 생각보다 오래 걸리지 않았습니다 20분에서 30분정도 고민해본 결과 풀이가
나왔으며 구현하는데 20분에서 30분정도
나머지는 역시나 틀린부분이나 반례를 찾는데 시간을 많이 사용했습니다.
개인적으로 수학공식이 필요한 문제가 아니라면 반례 찾는게 더 어려운 것 같습니다.
사설은 여기까지 하고 문제 풀이 적겠습니다.
곡괭이는 각각 최대 5개 이니 경우의 수만 15 팩토리오 라는 엄청 큰 수가 나오기 때문에 풀이에서 제외했습니다..
다음에 생각 했던 알고리즘은 DP 알고리즘 이였으나 문제를 계속 읽어보니 중요 키 포인트가 보였습니다.
제가 생각했던 중요한 키 포인트는 광물 5개를 무조건 연속적으로 캐야 하는 조건 이였습니다.
문제를 잘 보면 순서가 중요한 것 처럼 보이지만 저렇게 무조건 5번 연속으로 캐야하는 조건이 붙어있다면
5개씩 묶는다면 순서가 상관없어집니다.
또한 문제를 보시면 알겠지만 가장 큰 광물 5개 묶음이 있는 쪽에 다이아 곡괭이를 사용해야 최소값을 얻을 수 있습니다.
이 말은 즉 돌 곡괭이로 캤을 때 값이 가장큰 광물 묶음부터 차례대로 다이아로 처리해야한다는 뜻입니다.
이러한 점을 염두하고 문제를 풀면 될 것 같습니다.
제 아이디어 작성 노트입니다.
코드입니다. 주석처리를 최대한 해놓았습니다..
참고로 정렬은 퀵 슬롯으로 했으나
배열의 길이도 짧다 보니 버블 정렬로 해도 지장 없을 것 같습니다.
package Question;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 프로그래머스 광물 캐기
* https://school.programmers.co.kr/learn/courses/30/lessons/172927
*
*
* 아이디어
* 1. pick의 length 는 무조건 3
* 2. 문제 자체가 함정이 있는게 예시는 diamond만 얍삽하게 앞에다 위치시켜서 혼동을 줌
* 3. 오히려 반례 찾기가 더쉬움 stone이 앞열에 있으면 돌 곡괭이를 쓰는게 전략상 좋음
* 4. 정리하면 곡괭이는 한번 쓰면 5번은 무조건 사용해야하니깐 slice 알고리즘을 사용하면 됨 two point 알고리즘이였나..?
*
* 풀이
* 1. 길이가 5인 슬라이스를 돌려서 가장 많은 돌의 개수를 파악, 중요한점은 5개로 자른 리스트들은 섞어서 사용해도됨
* 2. 그리드 알고리즘이 통함
* 3. 그리고 곡괭이 갯수 * 5 가 전체 채광 길이보다 짧으면 마지막 인덱스를 거기로 해야함
* */
public class MiningForMinerals {
public static void main(String[] args) {
int[] param1 = new int[]{1,3,2};
String[] param2 = new String[]{"diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"};
System.out.println(solution(param1,param2));
int[] param3 = new int[]{0,1,1};
String[] param4 = new String[]{"diamond", "diamond", "diamond", "diamond", "diamond", "iron", "iron", "iron", "iron", "iron", "diamond"};
System.out.println(solution(param3,param4));
int[] param5 = new int[]{2,3,5};
String[] param6 = new String[]{"diamond", "diamond", "diamond", "diamond", "diamond", "iron", "iron", "iron", "iron", "iron", "diamond","diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"};
System.out.println(solution(param5,param6));
int[] param7 = new int[]{0,0,1};
String[] param8 = new String[]{"iron", "iron", "iron", "iron", "diamond","diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone","diamond", "diamond", "diamond", "diamond", "diamond", "iron"};
System.out.println(solution(param7,param8));
int[] param9 = new int[]{1,0,1};
String[] param10 = new String[]{"iron", "iron", "iron", "iron", "diamond"};
System.out.println(solution(param9,param10));
}
public static int solution(int[] picks, String[] minerals) {
int answer = 0;
int listNumber = minerals.length % 5 > 0 ? minerals.length / 5 + 1 : minerals.length / 5;
int mineNumber = minerals.length;
int pickaxNumber = 0;
// 곡괭이 갯수
for (int i : picks){
pickaxNumber += i;
}
pickaxNumber *= 5;
if(pickaxNumber < mineNumber) {
mineNumber = pickaxNumber;
listNumber = pickaxNumber / 5;
}
// {startIndex,endIndex,sum}
int[][] list = new int[listNumber][3];
int step = 0; // 넘어갈 step
int forStep = 0;
int sum = 0;
int startIndex = 0;
for (int i = 0; i < mineNumber; i++) {
char c = minerals[i].charAt(0);
if (c == 'd') sum += 25;
if (c == 'i') sum += 5;
if (c == 's') sum += 1;
if(forStep == 4 || i == mineNumber - 1){
list[step][0] = startIndex;
list[step][1] = i;
list[step][2] = sum;
step++;
forStep = 0;
sum = 0;
startIndex = i+1;
}else{
forStep++;
}
}
System.out.println(Arrays.deepToString(list));
quickSort(list , 0, list.length-1);
int result = 0;
// grid 알고리즘 진행
for (int i = list.length-1; i >= 0; i--){
int start = list[i][0];
int end = list[i][1];
int pickIndex = 0;
// 반복해서 값을 가져옴
for (int j = start; j <= end; j++) {
char c = minerals[j].charAt(0);
if(picks[0] > 0){
result += 1;
pickIndex = 0;
}else if(picks[1] > 0){
if (c == 'd') result += 5;
else result += 1;
pickIndex = 1;
} else if (picks[2] > 0) {
if (c == 'd') result += 25;
if (c == 'i') result += 5;
if (c == 's') result += 1;
pickIndex = 2;
}
}
picks[pickIndex] -= 1;
}
System.out.println(Arrays.deepToString(list));
return result;
}
// 값 변경, static 이여서 따로 반환하지 않아도 적용된다.
static void swap(int[]a, int idx1, int idx2){
int i = a[idx1];
a[idx1] = a[idx2];
a[idx2] = i;
}
static void swap(int[][]a, int idx1, int idx2){
int[] i = a[idx1];
a[idx1] = a[idx2];
a[idx2] = i;
}
static void quickSort(int[][] a, int left, int right){
int pl = left; // 왼쪽 커서
int pr = right; // 오른쪽 커서
int[] x = a[(pl + pr) /2]; // 피벗
do {
while(a[pl][2] < x[2]) pl++;
while(a[pr][2] > x[2]) pr--;
if(pl <= pr){
swap(a, pl++, pr--);
}
}while (pl <= pr);
if(left < pr) quickSort(a, left, pr);
if(pl < right) quickSort(a, pl, right);
}
}
