[Level2] 광물 캐기 (JAVA)

광물 캐기 문제 링크

정답 코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

class Solution {

    public int solution(int[] picks, String[] minerals) {
        int canDigCnt = Arrays.stream(picks).sum() * 5;
        if (minerals.length > canDigCnt) { // 광석의 개수가 곡괭이로 캘 수 있는 개수를 넘어간 상태
            minerals = Arrays.copyOfRange(minerals, 0, canDigCnt);
        }
        int n = minerals.length / 5;
        if (minerals.length % 5 != 0) {
            n++;
        }
        int[][] ar = new int[n][3];

        for (int i = 0, idx = 0; i < minerals.length; i += 5, idx++) {
            int j = i + 5 >= minerals.length ? minerals.length : i + 5;
            String[] tmp = Arrays.copyOfRange(minerals, i, j);
            ar[idx][0] = Arrays.stream(tmp).mapToInt((s) -> Mineral.from(s).getValue()).sum(); // 미네랄 피로도의 합산
            ar[idx][1] = i; // 시작 인덱스
            ar[idx][2] = j; // 끝 인덱스
        }
        Arrays.sort(ar, (a, b) -> b[0] - a[0]); // 내림차순 정렬

        Queue<Pickaxe> pickaxes = makePickaxes(picks);
        int result = 0;
        for (int i = 0; i < ar.length; i++) {
            Pickaxe pickaxe = pickaxes.poll();
            for (int j = ar[i][1]; j < ar[i][2]; j++) {
                result += pickaxe.digMineral(Mineral.from(minerals[j]));
            }
        }
        return result;
    }

    public Queue<Pickaxe> makePickaxes(int[] picks) {
        Queue<Pickaxe> pickaxes = new LinkedList<>();
        PickaxeFactory factory = new PickaxeFactory();
        for (int i = 0; i < picks.length; i++) {
            for (int j = 0; j < picks[i]; j++) {
                pickaxes.add(factory.create(i));
            }
        }
        return pickaxes;
    }
}

class PickaxeFactory {

    public Pickaxe create(int n) {
        if (n == 0) {
            return new DiamondPickaxe();
        }
        if (n == 1) {
            return new IronPickaxe();
        }
        return new StonePickaxe();
    }
}

interface Pickaxe {

    int digMineral(Mineral mineral);
}

abstract class AbstractPickaxe implements Pickaxe {

    int digDiamondStress, digIronStress, digStoneStress;

    @Override
    public int digMineral(Mineral mineral) {
        if (mineral == Mineral.DIAMOND) {
            return getDigDiamondStress();
        }
        if (mineral == Mineral.IRON) {
            return getDigIronStress();
        }
        return getDigStoneStress();
    }

    public int getDigDiamondStress() {
        return digDiamondStress;
    }

    public int getDigIronStress() {
        return digIronStress;
    }

    public int getDigStoneStress() {
        return digStoneStress;
    }
}

class DiamondPickaxe extends AbstractPickaxe {

    {
        digDiamondStress = 1;
        digIronStress = 1;
        digStoneStress = 1;
    }
}

class IronPickaxe extends AbstractPickaxe {

    {
        digDiamondStress = 5;
        digIronStress = 1;
        digStoneStress = 1;
    }
}

class StonePickaxe extends AbstractPickaxe {

    {
        digDiamondStress = 25;
        digIronStress = 5;
        digStoneStress = 1;
    }
}

enum Mineral {
    DIAMOND(31), IRON(6), STONE(1);

    private final int value;

    Mineral(int value) {
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public static Mineral from(String word) {
        return Mineral.valueOf(word.toUpperCase());
    }
}

문제 풀이

아이디어

• 5개 씩 광석을 나눈다.
• 나눈 구간의 시작과 끝 인덱스를 보관하고 광석들의 피로도 점수를 더한다.
  • 여기서 피로도 점수란 곡괭이에 상관없이 최악을 가정했을 때로 두어 다이아몬드 31, 철 6 돌 1로 두었다.
  • 왜 31, 6, 1점인가?
    • 예를 들어 돌이 연속으로 5개 있고 철 하나가 있을 때 철 하나가 코스트가 높았으면 좋겠다고 생각했다.
    • 철 = 돌 * 5 + 1; 다이아 = 철 * 5 + 1;
• 피로도 점수 기준 내림차순으로 정렬한다. - 내림차순 즉 피로도가 높은 것들을 먼저 처리할 수 있게 됨
• queue에 다이아 곡괭이부터 순서대로 넣는다.
• queue에서 꺼낸 곡괭이로 광석을 캐고 피로도의 총 합을 낸다.

주의할 점

• 캘 수 있는 광석의 최대 개수는 곡괭이 개수 * 5 이다.
• 한번 든 곡괭이는 내려놓을 수 없다.
• 주어진 순서대로만 광석을 캘 수 있다.(건너뛰거나 할 수 없음)
• 5개까지 캘 수 있다는 것에 사로잡히면 아래 문제가 생길 수 있음
  • 5개로 나눴을 때 가장 마지막 구역이 개수가 1개인데 피로도가 높아서 정렬 후 맨 앞에 있다.
  • 캐고 나서 4개나 더 캘 수 있다. 하지만 마지막 구역에 있던 것이므로 더 캘 수 있어도 곡괭이를 내려 놓아야한다.

아이디어에서 충분히 설명되어서 다른 건 생략하고 클래스에 대해서만 말하겠다.
어떤 곡괭이든 광석을 캐는 행동을 한다.
Pickaxe 인터페이스에 광석을 캐는 행동을 정의했다.
AbstractPickaxe는 곡괭이의 공통 속성을 가진다. 다이아몬드, 철, 돌을 캘 때의 각 피로도를 멤버변수로 가진다.
또한 Pickaxe의 구현체로서 미네랄의 종류에 따라 해당하는 피로도를 리턴해주도록 구현했다.
DiamondPickaxe, IronPickaxe, StonePickaxe 각 곡괭이들은 광석별로 피로도만 정의해주었다.
PickaxeFactory는 인덱스를 통해서 pickaxe를 만드는 역할을 한다.
Mineral은 광석을 정의하고 아이디어에서 말한 피로도를 설정해두었다.

느낀 점

주의할 점 마지막 포인트에서 너무 오래 걸렸다.
저거 하나 찾는데 몇시간이 소모되서 참.. 힘들었다.
2레벨은 아직 시간이 너무 오래 걸린다.

이번에 풀면서 디자인 패턴을 적용할 수 있을 것 같아서 고민 후에 템플릿 메소드 패턴과 팩토리 메소드 패턴을 적용해보았다.
이게 참 배운걸 이렇게 써먹는 구나 싶기도 하고 굉장히 뿌듯했다.
풀긴 풀었지만 solution method 가 너무 코드가 많아져서 신경쓰인다.
추후 분리 작업을 시도할 것이다.