[Java] 광물 캐기 - Lv2 프로그래머스

https://school.programmers.co.kr/learn/courses/30/lessons/172927#

프로그래머스

 

 

접근방법

---

idx : minerals배열을 총 반복 돌아야하는 횟수로 나머지가 남을경우 올림처리(ex : 18일때 4번돌아야함)
count : 광물 종류별 갯수 (처음에는 List<Map<String, Integer>>을 활용하여 풀려고 했다)

picksum : 총 광물을 캘 수 있는 수량(곡괭이 개수*5)

 

 

1. stone곡괭이의 경우의 수는 고려하지 않았다. 다이아, 철 곡괭이가 모두 소진된 후에 작업에 사용할 것이기 때문

2. minerals을 5개묶음으로 count배열에 담아준 다음, dia개수에 따른 내림차순 / dia개수가 같다면 iron개수에 따른 내림차순을 진행하여 가장 좋은 곡괭이로 작업을 해야하는 우선순위를 선별해주었다.

 

ex) minreals = {"diamond", "diamond", "diamond", "diamond", "iron", "diamond", "diamond", "iron", "iron", "iron", "diamond", "diamond", "iron", "iron", "stone", "diamond"}

광물을 dia순 내림차순 / 그 뒤에는 iron 내림차순으로 정렬한 모습이다.

dia가 2일 때, iron이 3인경우와 iron이 2인 경우가 있는데, iron 곡괭이가 있다면 당연히 iron 곡괭이로 캐는 것이 최적의 해를 구하는 방법일 것이다.

 

이처럼 광물등급이 높은 순으로 정렬을 하고, 곡괭이도 등급이 높은 순서대로 광물을 캔다면 최적의 해를 구할 수 있을 것이다.

int picksum = 0;
for(int i : picks) picksum+=i*5;

if(picksum >= minerals.length) {
    Arrays.sort(count, (o1, o2) -> {
        if(o1[0] == o2[0]) {
            return Integer.compare(o2[1], o1[1]);
        }
        else {
            return Integer.compare(o2[0], o1[0]);
        }
    });
}

위의 코드가 정렬을 위한 코드인데 우선 picksum변수를 선언하여 광물을 캘 수 있는 횟수를 구했다.

정렬 기준을 총 광물갯수보다 많이 캘 수 있을 경우로 주어, 5개로 묶은 광물들을 모두 정렬했다.

이차원 배열의 정렬은 조건만 잘 준다면 여러가지 방법으로 사용가능하며, 메서드체이닝도 활용할 수 있다.

 

 

첫 풀이

---

import java.util.Arrays;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        int idx = (int) Math.ceil((double)minerals.length / 5);        
        int[][] count = new int[idx][3];
        
        for(int i=0; i<idx; i++) {       	
        	for(int j=i*5; j<Math.min((i+1)*5, minerals.length); j++) {
        		switch(minerals[j]) {
        		case "diamond":
        			count[i][0]++;
        			break;
        		case "iron":
        			count[i][1]++;
        			break;        
        		case "stone":
        			count[i][2]++;
        			break;
        		}
        	}
        }
        int picksum = 0;
        for(int i : picks) picksum+=i*5;
        
        if(picksum >= minerals.length) {
            Arrays.sort(count, (o1, o2) -> {
            	if(o1[0] == o2[0]) {
            		return Integer.compare(o2[1], o1[1]);
            	}
            	else {
            		return Integer.compare(o2[0], o1[0]);
            	}
            });
        }
        
        int dia=picks[0]; int iron=picks[1]; int stone=picks[2];
        for(int i=0; i<idx; i++) {
        	if(dia > 0) {
        		answer += count[i][0] + count[i][1] + count[i][2];
        		dia--;
        	}
        	else if(iron > 0) {
        		answer += count[i][0]*5 + count[i][1] + count[i][2];
        		iron--;
        	}
        	else {
        		answer += count[i][0]*25 + count[i][1]*5 + count[i][2];
        		stone--;
        	}
        	picksum-=5;
        	if(picksum==0) {
        		return answer;
        	}
        }
        
        return answer;
    }
}

위의 과정들을 통해 처음 정답으로 작성한 코드지만, 13번 28번 케이스에서 통과하지 못했다.

생각해보니, 최대 캘 수 있는 갯수가 광물보다 많을 때만 생각하고, 반대의 경우는 생각하지 않았다.

 

 

두번째

---

내가 지금 짠 코드에서 수정을 할 수 있는 방법이 뭐가 있나 생각해봤다.

 

countsum변수를 하나 선언하고, 반복문 안에서 조건을 하나 넣어서 정렬을 진행했다.

만약 곡괭이가 없어 더이상 캐지 못하는데 광물이 남아있다면 캘 수 있는 경우의 배열만 정렬이 진행되도록 코드를 수정했다.

import java.util.Arrays;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        int idx = (int) Math.ceil((double)minerals.length / 5);        
        int[][] count = new int[idx][3];
        int picksum = 0;
        for(int i : picks) picksum+=i*5;
        int countsum = picksum;
        
        for(int i=0; i<idx; i++) {       	
        	for(int j=i*5; j<Math.min((i+1)*5, minerals.length); j++) {
        		switch(minerals[j]) {
        		case "diamond":
        			count[i][0]++;
        			break;
        		case "iron":
        			count[i][1]++;
        			break;        
        		case "stone":
        			count[i][2]++;
        			break;
        		}
        	}
            countsum -= 5;
            if(countsum == 0) {
                countsum = -1;
                Arrays.sort(count, (o1, o2) -> {
                    if(o1[0] == o2[0]) {
                        return Integer.compare(o2[1], o1[1]);
                    }
                    else {
                        return Integer.compare(o2[0], o1[0]);
                    }
                });
            }
        }
        
        if(picksum >= minerals.length) {
            Arrays.sort(count, (o1, o2) -> {
            	if(o1[0] == o2[0]) {
            		return Integer.compare(o2[1], o1[1]);
            	}
            	else {
            		return Integer.compare(o2[0], o1[0]);
            	}
            });
        }
        
        int dia=picks[0]; int iron=picks[1]; int stone=picks[2];
        for(int i=0; i<idx; i++) {
        	if(dia > 0) {
        		answer += count[i][0] + count[i][1] + count[i][2];
        		dia--;
        	}
        	else if(iron > 0) {
        		answer += count[i][0]*5 + count[i][1] + count[i][2];
        		iron--;
        	}
        	else {
        		answer += count[i][0]*25 + count[i][1]*5 + count[i][2];
        		stone--;
        	}
        	picksum-=5;
        	if(picksum==0) {
        		return answer;
        	}
        }
        
        return answer;
    }
}