[pg] 프로그래머스 광물캐기

1. 문제 정의

  곡괭이의 종류: 다이아, 철, 돌

  광물 종류: 다이아, 철, 돌

  이 있고, 곡괭이와 광물에 대한 리스트가 주어진다.

 

  각 곡괭이로 광물을 채집할 경우 피로도가 추가된다. 피로도는 각 곡괭이 및 광물의 클래스 별로 각각 다르다.

다이아 곡괭이로 광물을 채집할 경우 어떤 광물을 채집하던 피로도는 1이다.

철 곡괭이로 광물을 채집할 경우 철, 돌은 피로도 1, 다이아몬드는 피로도 5이다.

돌 곡괭이로 광물을 채집할 경우 돌은 피로도 1, 철은 5, 다이아몬드는 25이다.

 

광물은 연속해서 5개씩 캐는 과정을 진행한다. 채집 후 곡괭이는 사용완료.

5개 캐기전까지 곡괭이는 바꿀 수 없다.(캐는 중간에 곡괭이 교체 x)

채집 시작시 곡괭이는 리스트의 어떤 것을 선택해도 무방하다.

곡괭이가 없다면 채집종료.

 

위 조건을 가지고 곡괭이로 채집할 경우 최소 피로도 값을 구하는 것이 문제.

2. 내가 한 시도

 문제에서는 광물을 연속적으로 처리해야 한다고 적혀있었지만, 사실상 5개씩 쪼개면 순서를 바꿔도 상관이 없는 문제이다. 

 광물을 5개씩 묶어서 피로도 발생을 기준으로 광물 set을 내림차순 정렬하기로 하고 로직을 작성하였다.

 광물 별 피로도는 모두 달라야 하므로 돌 곡괭이의 피로도를 기준으로 피로도 계산을 진행하였다.

3. 코드

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Solution {

    public int solution(int[] picks, String[] minerals) {
        /*
         * 피로도 최솟값
         */
        int answer = 0;
        /*
         * 곡괭이가 없으면 더 이상 광물 채취 못하므로 뒤의 것은 의미가 없음.
         */
        int sumOfPicks = Arrays.stream(picks).sum();
        if (sumOfPicks == 0) return 0;
        minerals = Arrays.copyOfRange(minerals, 0, (sumOfPicks * 5));

        /*
         * 5개씩 잘라서 정렬하면 순서가 바뀌어도 상관이 없다. -> 5개씩 잘라서 stoneSum 기준으로 내림차 순 정렬
         */
        PriorityQueue<Sets> priorityQueue = new PriorityQueue<>((o1, o2) -> o2.getStoneSum() - o1.getStoneSum());

        for (int i = 0; i < minerals.length; i += 5) {
            String[] mineral = Arrays.copyOfRange(minerals, i, i + 5);
            priorityQueue.offer(new Sets(mineral));
        }

        /*
         * 우선순위큐에서 꺼내면서 피로도 sum
         */
        int picksIdx = 0;
        while (!priorityQueue.isEmpty()) {
            while (picks[picksIdx] == 0) {
                picksIdx++;
            }
            Sets poll = priorityQueue.poll();

            switch (picksIdx) {
                case 0:
                    answer += poll.getDiaSum();
                    break;
                case 1:
                    answer += poll.getIronSum();
                    break;
                case 2:
                    answer += poll.getStoneSum();
                    break;
            }
            /*
             * 쓴 곡괭이 폐기처리
             */
            picks[picksIdx] -= 1;
        }
        return answer;
    }

    class Sets {

        private String[] minerals;
        private int diaSum;
        private int ironSum;
        private int stoneSum;


        public Sets(String[] minerals) {
            this.minerals = minerals;
            this.diaSum = 0;
            this.ironSum = 0;
            this.stoneSum = 0;

            for (int i = 0; i < minerals.length; i++) {
                String mineral = minerals[i];
                if (mineral == null) break;
                switch (mineral) {
                    case "diamond":
                        diaSum += 1;
                        ironSum += 5;
                        stoneSum += 25;
                        break;
                    case "iron":
                        diaSum += 1;
                        ironSum += 1;
                        stoneSum += 5;
                        break;
                    case "stone":
                        diaSum += 1;
                        ironSum += 1;
                        stoneSum += 1;
                        break;

                }
            }

        }

        public String[] getMinerals() {
            return minerals;
        }

        public int getDiaSum() {
            return diaSum;
        }

        public int getIronSum() {
            return ironSum;
        }

        public int getStoneSum() {
            return stoneSum;
        }
    }
}

4. 회고

 문제에서는 곡괭이는 자율적으로 선택가능하고, 광물은 연속적으로 캐야하기 때문에 광물이 fix되어 있는 것 처럼 느껴지는 문제였지만, 실상은 5개씩 쪼개서 광물의 순서를 정렬하여 최소한의 피로도를 구하는 것이 핵심이었던 문제였다.

 

참조

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