[ Programmers - LV2 ] 광물 캐기

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

프로그래머스

 

요즘 그리디 문제를 자주 접하고 있는데, 어느 정도 감만 잡으면 풀 수 있는 문제들도 슬슬 나오기 시작 했다.

그리디 문제들을 내가 접하면 어떻게 풀지 하고 뇌정지되는 경우가 많았었는데(사실 지금도) 어떻게든 일단 코드를 치기 시작하면 통과하지 못하더라도 진행은 되더라

---

📌 분석

• 입력되는 광물 순서를 변경 불가능함
• 곡괭이
  • 내구도 5 (5개의 광물까지 채광 가능하다)
  • 한 번 사용을 시작하면 내구도가 끝날 때 까지 사용 해야한다.
  • 모든 곡괭이가 소진될 때까지 채광 지속 가능하다.
  • 다이아 / 철 / 돌 3 가지 분류의 곡괭이가 있고 아래와 같이 피로도가 누적된다.
    • 다이아: 1 / 1 / 1
    • 철: 5 / 1 /  1
    • 돌: 25 / 5 / 1
• 광물
  • 다이아 / 철 / 돌 3 가지 분류를 갖는다.

※ 곡괭이 혹은 광물이 전부 소진될 때 까지 채광을 지속한다.

---

📌 풀이

기본적으로 그리디 문제는 이름 그대로 욕심을 부려서 가장 이득을 볼 수 있는 상황을 만들어 내는 것인데, 문제에서 가장 이득을 취할 수 있는 부분은 피로도를 최소화 할 수 있는 다이아 광물 - 다이아 곡괭이 케이스이다.

 

그래서 나는 5 개씩 광물을 덩어리로 잘라서 다이아가 가장 많은 덩어리 부터 가장 성능이 좋은 곡괭이를 사용하도록 하였다. 

 

내가 만든 예시를 예를 들어서 문제를 풀어 보자면 (테스트 케이스 8번이 여러번 실패해서 다른 사람들 질문 보고 만든 케이스)

picks (곡괭이)	minerals (광물)
{1,1,0}	{"diamond","diamond","diamond","iron","iron","diamond","iron","stone","iron","iron","diamond","diamond"}

 

[ 예시 시각화 ]

주어진 곡괭이가 2개이기 때문에 총 2덩이 밖에 만들어지지 못한다.

주어진 다이아 곡괭이 1개 / 아이언 곡괭이 1개 이기 때문에 뒤에 입력으로 들어오는 광물은 덩어리로 분리할 때 신경쓰지 않는다.

 

위에서는 정렬이 필요 없지만 만약에 다이아 3개 짜리 덩어리와 1개 짜리 덩어리 순서가 바뀌었다면 두 덩어리의 순서도 변경 해줘야 한다.

곡괭이는 가장 좋은것 부터 사용하기 때문에 아래와 같이 계산된다.

 

• 다이아 곡괭이: 1 + 1 + 1 + 1 + 1 = 5
• 아이언 곡괭이: 5 + 1 + 1 + 1 + 1 = 9
• Answer: 14

---

📌 예외 케이스

앞서서 말했던 케이스 8번이 문제가 되었었는데, 광물이 순서대로 들어오는 것과 곡괭이가 모든 광물을 처리할 수 없는 수량이 들어올 수도 있기 때문에 고려 했어야 하는 상황이다.

 

[ 예외 케이스 시각화 ]

나 같은 경우에는 곡괭이 숫자에 상관 없이 모든 광물들을 리스트에 받아서 정렬했기 때문에 지금 위에 보이는 2 번째와 3 번째 덩어리가 정렬되면서 위치가 변경되면서 값이 제대로 나오지 않는 상황이 생겼다.

 

• 다이아 곡괭이: 1 + 1 + 1 + 1 + 1 = 5
• 아이언 곡괭이: 5 + 5 = 10
• Wrong Answer: 15
• Collect Answer: 14

---

📌 부분 코드 - Java

if(totalPick == 0) break;  // 곡괭이 숫자가 부족하면 광물은 남았어도 더 이상 집계하지 않음

리스트를 만드는 부분에서 곡괭이 숫자를 감산 하다가 0 개가 된다면 광물 입력 받는걸 종료 한다.

 

if(totalPick != 0 && (dia != 0 || iro != 0 || sto != 0)) {  // 5 개 묶음이 아닌 케이스
    masses.add(new Mass(dia, iro, sto));
}

마지막 부분에서 광물이 5 개 전부 입력이 안될 수 있어서 따로 처리 해주었다.

내 코드의 경우 클래스로 묶기 때문에 무조건 new Mass(dia, iro, sto) 를 실행하면 모든 광물이 0 개인 덩어리가 만들어질 수 있다.

 

@Override
public int compareTo(Mass mass) {
    int diaRes = Integer.compare(mass.dia, this.dia);
    if(diaRes != 0) return diaRes;

    int ironRes = Integer.compare(mass.iro, this.iro);
    if(ironRes != 0) return ironRes;

    return Integer.compare(mass.sto, this.sto);
}

먼저 다이아가 가장 많은 순서대로 정렬 하기 위해서 다이아의 갯수를 내림 차순으로 정렬 하는데, 다이아의 개수가 같다면 아이언을 비교하고, 아이언 수도 같다면 돌맹이의 정렬 순서로 반환한다. (사실 다이아, 아이언의 개수가 같다면 돌맹이의 수도 같을 수 있지만, 5개의 광물이 다 입력안된 케이스도 있기 때문에 정렬이 필요)

---

📌 최종 코드 - Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[] picks, String[] minerals) {
        List<Mass> masses = getSortedMasses(Arrays.stream(picks).sum(), minerals);
        int ans = 0;

        for(Mass mass : masses) {
            if(picks[0] != 0) {
                ans += mass.getFatigue(25);
                picks[0]--;
            } else if(picks[1] != 0) {
                ans += mass.getFatigue(5);
                picks[1]--;
            } else if(picks[2] != 0) {
                ans += mass.getFatigue(1);
                picks[2]--;
            } else {
                break;
            }
        }

        return ans;
    }

    private List<Mass> getSortedMasses(int totalPick, String[] minerals) {
        List<Mass> masses = new ArrayList<>();
        int cnt = 0;
        int dia = 0;
        int iro = 0;
        int sto = 0;

        for(String mineral : minerals) {
            if(totalPick == 0) break;

            switch(mineral.charAt(0)) {
                case 'd': dia++; break;
                case 'i': iro++; break;
                case 's': sto++; break;
                default: // Unreachable Code
            }

            cnt++;

            if(cnt == 5) {
                masses.add(new Mass(dia, iro, sto));
                cnt = 0;
                dia = 0;
                iro = 0;
                sto = 0;
                totalPick--;
            }
        }

        if(totalPick != 0 && (dia != 0 || iro != 0 || sto != 0)) {
            masses.add(new Mass(dia, iro, sto));  // 5 개 묶음이 아닌 케이스
        }

        return masses.stream().sorted(Mass::compareTo).collect(Collectors.toList());
    }
}

class Mass implements Comparable<Mass>{
    int dia;
    int iro;
    int sto;

    public Mass(int dia, int iro, int sto) {
        this.dia = dia;
        this.iro = iro;
        this.sto = sto;
    }

    public int getFatigue(int pick) {
        return calcEachFatigue(pick, dia, 25) +
               calcEachFatigue(pick, iro, 5) +
               calcEachFatigue(pick, sto, 1);
    }

    public int calcEachFatigue(int pick, int mineral, int value) {
        int sum = 0;

        while(mineral-- > 0) {
            int res = value / pick;
            sum += (res == 0) ? 1 : res;
        }

        return sum;
    }

    @Override
    public int compareTo(Mass mass) {
        int diaRes = Integer.compare(mass.dia, this.dia);
        if(diaRes != 0) return diaRes;

        int ironRes = Integer.compare(mass.iro, this.iro);
        if(ironRes != 0) return ironRes;

        return Integer.compare(mass.sto, this.sto);
    }
}

---

📌 결과

[ 결과 - Java ]

---

📌  마치며...

요즘 정렬과 그리디 문제들을 자주 마주치는데 단골 문제인 만큼 더 익숙해질 필요가 있다고 느끼고 있다.

그리고 정렬과 같은 문제를 풀다 보니까 내가 정렬 알고리즘들을 지금 누구에게 설명해줄 수 있을까 생각하다 보니까 할 수 없겠더라..

그래서 문제 풀이도 좋지만 알고리즘에 대해서 블로그에 정리를 하면 좋겠다 싶은데.... 쉽지는 않겠지...