프로그래머스, 광물 캐기(java)

문제 설명

곡괭이로 광물을 캐려고 한다. 곡괭이와 공물은 각각 다이아몬드, 철, 돌이 존재하는데, 어떤 곡괭이로 어떤 광물을 캐려는지에 따라 피로도가 다르다. 또한 각 곡괭이는 종류에 상관 없이 광물 5개를 캔 후에는 더 이상 사용할 수 없다. 곡괭이는 순서대로 사용하지 않아도 되지만, 광물은 순서대로 캐야 한다. 또한 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용한다.

 

광물을 모두 캐거나 곡괭이를 모두 사용해서 광물을 캐려고 할 때, 나올 수 있는 피로도의 최솟값을 구하여라

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

프로그래머스

주의

해당 문제를 처음 풀 때 내가 잘못 생각한 게 있는데, 피로도는 곡괭이의 내구도와는 상관이 없다는 점이다.

즉, 철 곡괭이로 다이아몬드를 하나 캐서 피로도가 5가 든다고 해도 해당 철 곡괭이는 총 4번을 더 캘 수 있다. 하나의 광물을 캘 때마다 피로도가 주어진다는 의미이지, 해당 피로도가 곡괭이의 내구도인 5에 영향을 미치지 않는다는 의미이다.

문제 풀이

솔직히 문제를 처음 봤을 때 어떻게 푸는지 감을 잡기 어려웠다. 그래서 질문하기를 살펴보니 광물들을 다섯 개로 나누라는 힌트를 보았다. 곡괭이 하나를 잡으면 총 다섯 개의 광물을 캐야 하니까, 해당 세션 별로 각 곡괭이를 캤을 때의 피로도를 구하라는 의미이다.

 

예를 들어서 문제의 첫 번째 예의 minerals부분을 보자.

[다이아, 다이아, 다이아, 철, 철, 다이아, 철, 돌]

이렇게 되어 있을 때 광물을 다섯 개로 나누면 [다이아, 다이아, 다이아, 철, 철], [다이아, 철, 돌]이 된다. 각 세션은 하나의 곡괭이로 캘 수 있는 전체 광물이다.

 

그렇다면 다이아 곡괭이로 첫 번째 세션을 캐면 얼마 만큼의 피로도가 들까?

정답은 5이다. 왜냐하면 다이아 곡괭이로는 모든 광물을 피로도 1로 캘 수 있기 때문이다.

쇠 곡괭이로 캐면 17이 나온다. 그리고 돌 곡괭이로 캐면 85가 나온다.

 

두 번째 세션의 경우에는 다이아로는 3, 철로는 5, 돌로는 31만큼의 피로도가 생긴다.

주의 점

여기서 조심해야 할 부분이 바로 8번 케이스이다.

만일 곡괭이 수가 광물의 총 수보다 적으면 어떻게 될까?

광물은 순서대로 캔다고 했으므로 당연히 곡괭이 수를 벗어나는 부분은 캐지 못할 것이다. 이 부분을 간과하고 넘어간다면 정렬을 했을 때 곡괭이 수를 벗어나는 부분이 앞 쪽으로 와 계산되어 버리는 문제가 생긴다. 그러므로 곡괭이를 벗어난 부분은 모두 0처리를 해줘야 한다.

 

        int answer = 0;
        int a = minerals.length/5;
        int b = minerals.length%5;
        int index = 0;
        int[][] section;
        int picksNum = picks[0] + picks[1] + picks[2];
        
        //각 곡괭이 별 피로도
        if(b == 0){
            section = new int[a][3];
        }else{
            section = new int[a+1][3];
        }
        
        for(int i=0; i<a; i++){
            for(int j=index; j<index+5; j++){
                char m = minerals[j].charAt(0);
                if(m == 'd'){
                    section[i][0] += 1;
                    section[i][1] += 5;
                    section[i][2] += 25;
                }else if(m == 'i'){
                    section[i][0] += 1;
                    section[i][1] += 1;
                    section[i][2] += 5;
                }else if(m == 's'){
                    section[i][0] += 1;
                    section[i][1] += 1;
                    section[i][2] += 1;
                }
            }
            index += 5;
        }
        
        if(b != 0){
            for(int i=index; i<minerals.length; i++){
                char m = minerals[i].charAt(0);
                if(m == 'd'){
                    section[a][0] += 1;
                    section[a][1] += 5;
                    section[a][2] += 25;
                }else if(m == 'i'){
                    section[a][0] += 1;
                    section[a][1] += 1;
                    section[a][2] += 5;
                }else if(m == 's'){
                    section[a][0] += 1;
                    section[a][1] += 1;
                    section[a][2] += 1;
                }
            }
        }
        
        if(section.length > picksNum){
            for(int i=picksNum; i<section.length; i++){
                section[picksNum][0] = 0;
                section[picksNum][1] = 0;
                section[picksNum][2] = 0;
            }
        }

 

이렇게 각 세션 별로 피로도를 구해준 다음에는 뭘해야 할지 생각을 해보자.

일단 다이아 곡괭이로 캐는 것이 피로도가 제일 적게 쌓인다. 이 말은 즉, 돌로 캤을 때 제일 피로도가 많이 쌓으는 세션을 다이아로 캐면 무조건 피로도가 5가 나오므로 이득이라는 의미이다. 다이아 곡괭이를 모두 사용했다면 남아있는 세션 중 제일 피로도가 많은 부분을 철로 캐고 철 곡괭이가 다 떨엊지면 마지막 부분을 돌 곡괭이로 캐면 되는 것이다.

 

이를 위해서 각 세션 별 곡괭이 피로도를 정렬해주면 된다.

 

기준은 돌 곡괭이이고 만일 돌 곡괭이가 같을 경우 철, 둘 다 같을 경우 돌로 해주면 된다.

        Arrays.sort(section, (o1, o2) ->{
            if(o1[2] == o2[2]){
                return o2[1]-o1[1];
            }else if(o1[2] == o2[2] && o1[1] == o2[1]){
                return o2[0] - o1[0];
            }
            return o2[2] - o1[2];
        });

각 세션을 모두 정렬해줬다면 이제는 곡괭이를 돌면서 계산을 해줄 차례이다.

각 곡괭이 별로 그 수를 pick에 옮겨준다. 그리고 pick이 0이 아닐 때까지 각 세션 별로 해당 곡괭이의 피로도를 더해주면 된다. 이때 각 세션의 인덱스가 세션의 크기와 같거나 커진다면 탈출한다.

        index = 0;
        boolean flag = true;
        //각 곡괭이를 돌면서 하나씩 빼줌
        for(int i=0; i<3; i++){
            int pick = picks[i];
            while(pick != 0){
                if(index >= section.length){
                    flag = false;
                    break;
                }
                answer += section[index][i];
                pick -= 1;
                index += 1;
            }
            
            if(!flag){
                break;
            }
        }

코드

java

import java.util.*;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        int answer = 0;
        int a = minerals.length/5;
        int b = minerals.length%5;
        int index = 0;
        int[][] section;
        int picksNum = picks[0] + picks[1] + picks[2];
        
        //각 곡괭이 별 피로도
        if(b == 0){
            section = new int[a][3];
        }else{
            section = new int[a+1][3];
        }
        
        for(int i=0; i<a; i++){
            for(int j=index; j<index+5; j++){
                char m = minerals[j].charAt(0);
                if(m == 'd'){
                    section[i][0] += 1;
                    section[i][1] += 5;
                    section[i][2] += 25;
                }else if(m == 'i'){
                    section[i][0] += 1;
                    section[i][1] += 1;
                    section[i][2] += 5;
                }else if(m == 's'){
                    section[i][0] += 1;
                    section[i][1] += 1;
                    section[i][2] += 1;
                }
            }
            index += 5;
        }
        
        if(b != 0){
            for(int i=index; i<minerals.length; i++){
                char m = minerals[i].charAt(0);
                if(m == 'd'){
                    section[a][0] += 1;
                    section[a][1] += 5;
                    section[a][2] += 25;
                }else if(m == 'i'){
                    section[a][0] += 1;
                    section[a][1] += 1;
                    section[a][2] += 5;
                }else if(m == 's'){
                    section[a][0] += 1;
                    section[a][1] += 1;
                    section[a][2] += 1;
                }
            }
        }
        
        if(section.length > picksNum){
            for(int i=picksNum; i<section.length; i++){
                section[picksNum][0] = 0;
                section[picksNum][1] = 0;
                section[picksNum][2] = 0;
            }
        }
        //돌 -> 철 -> 다이아 순으로 정렬
        Arrays.sort(section, (o1, o2) ->{
            if(o1[2] == o2[2]){
                return o2[1]-o1[1];
            }else if(o1[2] == o2[2] && o1[1] == o2[1]){
                return o2[0] - o1[0];
            }
            return o2[2] - o1[2];
        });
        
        for(int i=0; i<section.length; i++){
            System.out.println(section[i][0] + " " + section[i][1] + " " + section[i][2]);
        }
        
        index = 0;
        boolean flag = true;
        //각 곡괭이를 돌면서 하나씩 빼줌
        for(int i=0; i<3; i++){
            int pick = picks[i];
            while(pick != 0){
                if(index >= section.length){
                    flag = false;
                    break;
                }
                answer += section[index][i];
                pick -= 1;
                index += 1;
            }
            
            if(!flag){
                break;
            }
        }
        
        
        return answer;
    }
}