[Programmers] 광물 캐기

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

프로그래머스

문제 설명

문제가 상당히 길기 때문에 꼼꼼히 읽어야 한다.

 

우리는 광부가 되어 광산에서 광물을 캐야 한다. 주어지는 곡괭이 종류는 다이아, 철, 돌이며 캘 수 있는 광물도 마찬가지다. 각 곡괭이의 내구도는 5라서 광물 종류와 상관없이 5번을 캐면 더 이상 사용할 수 없다.

우리는 사람이기 때문에 작업을 하면 피로도가 쌓인다. 다이아 곡괭이는 너무 좋아서 어떤 광물을 캐든 피로도가 1만 쌓인다. 철 곡괭이로는 다이아를 캐면 피로도가 5, 철이나 돌을 캐면 피로도가 1만큼 쌓인다. 돌 곡괭이로는 다이아를 캐면 25, 철을 캐면 5, 돌을 캐면 1만큼 피로도가 쌓인다.  우리가 최대한 피곤하지 않게 피로도를 최소한으로 해서 광물을 캐야 한다.

 

다만 채광 시 다음과 같은 규칙을 지켜야 한다.

• 사용할 수 있는 곡괭이 중 아무거나 하나를 선택해서 광물을 캔다.
• 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용한다.
• 광물은 주어진 순서대로만 캐야 한다.
• 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캐야 한다.

 

따라서 곡괭이를 하나 선택해서 광물을 5개 연속으로 캐고, 다음 곡괭이를 선택해서 광물 5개를 연속으로 캐는 작업을 마지막 조건에 걸릴 때까지 반복하는 것이다.

이때 최소한의 피로도를 반환하는 함수를 작성해야 한다.

입력 조건

• int[] picks: 곡괭이 개수. 0번 인덱스부터 다이아, 철, 돌 곡괭이가 순서대로 주어진다.
  • 최소 0개 이상, 최대 5개 이하로 주어진다.

• String[] minerals: 광물들
  • 최소 5개 이상, 최대 50개 이하로 주어진다.

풀이 방법

최소한이라는 단어를 보고 그리디 문제라고 생각했다. 그래서 고려해야할 조건들을 생각해보았다.

• 하나의 곡괭이를 정하면 그대로 5개를 캐야 한다.
• 주어진 순서대로 5개씩 곡괭이를 정하는 게 아니라 모든 광물을 보고 적합한 순서에 적합한 곡괭이를 사용해야 한다.

 

이 조건을 만족하기 위해 떠오른 방법은 정렬이다. 주어진 광물들을 5개씩 분리한 다음 다이아, 철, 돌의 개수별로 정렬하는 것이다. 예를 들어 [다이아, 다이아, 철, 돌 돌, 다이아 다이아, 다이아, 돌, 돌] 로 주어지면 앞에서부터 5개씩 잘라서 [다이아, 다이아, 철, 돌, 돌], [다이아, 다이아, 다이아, 돌, 돌]로 분리하고 다이아 > 철 > 돌의 개수별로 정렬해서 [ [ 다이아, 다이아, 다이아, 돌, 돌], [다이아, 다이아, 철, 돌, 돌] ] 로 만드는 것이다. 그 다음에는 다이아 곡괭이부터 가진 개수만큼 광물을 캐면 되는 것이다.

 

다만 이때 주의해야 할 점이 있는데 바로 위에서 언급한 채광 조건 중 '광물은 주어진 순서대로만 캐야 한다'는 사항이다. 위처럼 정렬하면 기존의 순서를 뒤바꿨기 때문에 이 조건을 만족하지 못한다. 예를 들어 곡괭이가 [0, 1, 0] 으로 주어지고 광물이 [돌, 돌, 돌, 돌, 돌, 다이아, 다이아, 다이아, 다이아] 로 주어지면 이를 위처럼 정렬 시 [ [ 다이아x4 ], [ 돌x5 ] ] 로 정렬이 되므로 다이아를 먼저 캐버린다. 이에 대한 해결법은 간단하다. 광물들은 정렬하기 전에 순서대로 5개씩 분리되어 있다. 그러면 [ [ 돌x5 ], [ 다이아x4 ] ] 가 된다. 이때 만약 곡괭이 총 개수보다 캘 광물들이 더 많다면 묶인 광물 개수 - 곡괭이 총 개수만큼 반복을 돌면서 리스트의 맨 마지막 요소를 삭제하면 된다. 예의 경우 [ 다이아x4 ] 가 삭제될 것이다. 어차피 못 캘 광물들이기 때문에 메인 로직을 간단히 하기 위해 전처리를 하는 것이다.

 

이 작업이 끝나면 그 다음은 순탄하다. 다이아 > 철 > 돌 순으로 리스트를 정렬하고 다이아, 철, 돌 곡괭이 순으로 채광하고 피로도를 계산하면 된다. 코드는 다음과 같다.

import static java.util.Collections.frequency;
import java.util.*;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        /***
          * minerals 배열을 5개 단위로 subset
          * diamond, iron, stone 순으로 내림차순 정렬
          * 앞에서부터 채광
          */
        int answer = 0;

        List<List<String>> list = new ArrayList<>();
        for (int i = 0; i < minerals.length / 5 + 1; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < minerals.length / 5 + 1; i++) {
            for (int j = 0 + i * 5; j < 5 + i * 5; j++) {
                if (j >= minerals.length) break;
                list.get(i).add(minerals[j]);
            }
        }

        // 광물이 5로 나누어 떨어질 때는 불필요하게 리스트 1개가 더 생기므로 제거
        if (minerals.length % 5 == 0) {
            list.remove(list.size() - 1);
        }

        // 만약 곡괭이 수보다 자원의 개수가 더 많아서 모두 캐지 못할 경우 캐지 못하는 미네랄은 삭제
        int pickax = picks[0] + picks[1] + picks[2];
        if (pickax < list.size()) {
            int countWillRemove = list.size() - pickax;
            for (int i = 0; i < countWillRemove; i++) {
                list.remove(list.size() - 1);
            }
        }

        // 다이아, 철, 돌 개수 순으로 리스트 내림차순 정렬
        Collections.sort(list, (l1, l2) -> {
            if (frequency(l2, "diamond") == frequency(l1, "diamond")) {
                if (frequency(l2, "iron") == frequency(l1, "iron")) {
                    return frequency(l2, "stone") - frequency(l1, "stone");
                } else {
                    return frequency(l2, "iron") - frequency(l1, "iron");
                }
            } else {
                return frequency(l2, "diamond") - frequency(l1, "diamond");
            }
        });

        // 다이아 곡괭이로 채광
        for (int i = 0; i < picks[0]; i++) {
            if (list.isEmpty()) break;
            List<String> curL = list.get(0);
            for (int j = 0; j < curL.size(); j++) {
                answer += 1;
            }
            list.remove(0);
        }

        // 철 곡괭이로 채광
        for (int i = 0; i < picks[1]; i++) {
            if (list.isEmpty()) break;
            List<String> curL = list.get(0);
            for (int j = 0; j < curL.size(); j++) {
                if (curL.get(j).equals("diamond")) answer += 5;
                else answer += 1;
            }
            list.remove(0);
        }

        // 돌 곡괭이로 채광
        for (int i = 0; i < picks[2]; i++) {
            if (list.isEmpty()) break;
            List<String> curL = list.get(0);
            for (int j = 0; j < curL.size(); j++) {
                if (curL.get(j).equals("diamond")) answer += 25;
                else if (curL.get(j).equals("iron")) answer += 5;
                else answer += 1;
            }
            list.remove(0);
        }

        return answer;
    }
}

회고

다른 분들의 해답을 보니 대부분 DFS나 BFS로도 많이 푸신 것을 보았다. 그 방법으로 풀 수 있다는 게 놀라웠다(그래도 제출해보면 내 답이 시간상으로나 메모리상으로나 더 빨라서 뿌듯했다).