[Lv.2] 광물 캐기 [프로그래머스_코딩테스트] [구현, 최적 선택] [40분]

🔍 문제 요약

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

프로그래머스

3가지의 광물 종류와 동일한 3가지의 곡괭이 종류가 주어지고 각각 서로 매칭했을 때의 피로도가 주어진다. 이때 곡괭이(pick)의 갯수 배열이 주어지고 광물들을 캐는 순서가 주어질 때 최소한의 피로도를 찾는 방법 구하기. (곡괭이 한 번 사용시 5번 고정으로 연달아 사용해야 함)

🧠 나의 접근 방식과 시행착오

문제는 풀다가 중간에 멈추었기에 내가 코드를 짜려고 시도한 방식에 대해서 정리를 하려고 코드와 같이 몇글자 적어본다. 일단 핵심으로 생각되는 부분이 문자열로 된 minerals를 곡괭이와 매칭을 위해서 숫자로 바꿔서 List<int>로 저장을 하고, 5개씩 묶어서 평균을 값을 구한 avgList를 만들었다. 5개를 연달아 캐야 하고 최적의 효율을 내려면 평균치보다 숫자가 같거나 (최대효율) 작은 경우 (피로도 1)에 효율이 좋다. (광물보다 숫자가 큰 곡괭이를 사용하면 피로도가 5배씩 차이 남) 그렇게 접근은 했으나 생각보다 시간을 잡아 먹었고 풀이가 길어지고 있는 것을 깨닫고 gpt에게 문제의 풀이법을 받아서 공부를 해보기로 하였다.

using System;
using System.Collections.Generic;

public class Solution
{
    /// <summary>
    /// 광물 캐기
    /// https://school.programmers.co.kr/learn/courses/30/lessons/172927
    /// </summary>
    public int solution(int[] picks, string[] minerals)
    {
        // 곡괭이 휘두르는 횟수 5로 고정
        const int SwingCount = 5;
        // 미리 정해진 것
        var energyDict = new Dictionary<(int, int), int>()
        {
            { (0, 0), 1 },
            { (0, 1), 1 },
            { (0, 2), 1 },
            { (1, 0), 5 },
            { (1, 1), 1 },
            { (1, 2), 1 },
            { (2, 0), 25 },
            { (2, 1), 5 },
            { (2, 2), 1 },
        };

        // mineral 이름을 pick과 비교하기 위해 숫자로 치환
        var mineralsKey = new Dictionary<string, int>()
        {
            { "diamond", 0 },
            { "iron", 1 },
            { "stone", 2 },
        };
        
        // 먼저 미네랄을 숫자로 바꿔서 배열로 넣는다.
        int[] mineralArray = new int[minerals.Length];

        for (int i = 0; i < minerals.Length; i++)
        {
            mineralArray[i] = mineralsKey[minerals[i]];
        }
        
        Span<int> mineralSpan = new Span<int>(mineralArray);
        int index = 0;
        List<int> avgList = new List<int>();

        while (index < minerals.Length)
        {
            int length = (index + SwingCount < minerals.Length) ? SwingCount : minerals.Length - index;
            var test = mineralSpan.Slice(index, length);
            int sum = 0;

            foreach (var data in test)
            {
                sum += data;
            }
            
            // 5개 묶음의 평균보다 같거나 큰걸 우선해야 피로도가 낮아짐.
            int avg = sum / length;
            avgList.Add(avg);

            index += SwingCount;
        }
        
        foreach (int avg in avgList)
        {
            int choice = -1;
            
            for (int i = 0; i < picks.Length; i++)
            {
                if (picks[i] <= 0) continue;
                
                // 베스트 케이스
                if (avg == i)
                {
                    choice = i;
                }
            }
        }

        
        
        int answer = 0;
        return answer;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
    }
}

 

✅ 풀이 코드

풀이 코드를 보니 역시 생각보다 길고 복잡한 풀이코드가 나온 듯 하다. 풀이를 해석해 보면 결국 string[] minerals를 5개씩 묶음으로 해서 List<string[]> mineralsChunks에 저장한다. 안전장치를 넣어서 곡괭이의 전체 합 (picks)보다 작게 리스트를 유지한다. 사실 1번의 프로세스는 필자도 동일한 생각을 가지고 풀이를 하려고 했던 부분 (필자는 int로 바꾸고 평균을 계산 해서 곡괭이를 선택하려고 했음) 2번의 프로세스가 좀 list가 길어져 있는데 튜플로 아까 chunk 리스트의 각 스트링 배열과 다이아, 철, 돌에 곡괭이를 골랐을 때 피로도의 합산치를 구한 리스트를 만들어 낸 것을 알 수 있다. (fatigueList)  그 후 곡괭이를 선택하는 것을 쉽게 하기 위해서 피로도가 가장 높은 묶음이 생기는 돌로 해서 정렬을 한 후 곡괭이를 다이아 > 철 > 돌의 순서대로 빼가면서 값을 구한 것을 알 수 있다. 조금 길어져서 한 번에 해당 코드까지 만들어 내기는 생각보다 번거롭지 않을까 싶긴 하다는 생각이 든다.

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int[] picks, string[] minerals) {
        int answer = 0;

        // 1. 광물 묶음 단위로 나누기 (5개씩)
        List<string[]> mineralChunks = new List<string[]>();
        for (int i = 0; i < minerals.Length && mineralChunks.Count < (picks[0] + picks[1] + picks[2]); i += 5) {
            int len = Math.Min(5, minerals.Length - i);
            var chunk = new string[len];
            Array.Copy(minerals, i, chunk, 0, len);
            mineralChunks.Add(chunk);
        }

        // 2. 각 묶음의 피로도 정보 계산 (정렬 기준용)
        var fatigueList = new List<(int dia, int iron, int stone, string[] data)>();
        foreach (var chunk in mineralChunks) {
            int dia = 0, iron = 0, stone = 0;
            foreach (var m in chunk) {
                switch (m) {
                    case "diamond":
                        dia += 1; iron += 5; stone += 25;
                        break;
                    case "iron":
                        dia += 1; iron += 1; stone += 5;
                        break;
                    case "stone":
                        dia += 1; iron += 1; stone += 1;
                        break;
                }
            }
            fatigueList.Add((dia, iron, stone, chunk));
        }

        // 3. 가장 피로도 높은 묶음부터 처리 → 좋은 곡괭이 우선
        fatigueList.Sort((a, b) => b.stone.CompareTo(a.stone)); // 가장 피로도 높은 묶음부터

        int pickIndex = 0;

        foreach (var (dia, iron, stone, chunk) in fatigueList) {
            int fatigue = 0;

            // 다이아 곡괭이
            if (picks[0] > 0) {
                fatigue = dia;
                picks[0]--;
            }
            // 철 곡괭이
            else if (picks[1] > 0) {
                fatigue = iron;
                picks[1]--;
            }
            // 돌 곡괭이
            else if (picks[2] > 0) {
                fatigue = stone;
                picks[2]--;
            }

            answer += fatigue;
        }

        return answer;
    }
}

 

🔄 정리

2, 3번 프로세스에서 하나로 묶은 fatigueList를 활용하는 부분을 배울만한 점이라고 생각이 된다. 사실상 3가지를 한 세트로 해서 종류별 피로도의 합산을 해서 정렬을 할 수 있는 방향성에 대해서도 다음에 써먹을만한 방법이라고 생각이 듬. 매번 리스트를 생각하면 기본 자료형 애들만 주로 넣거나 class나 struct로 분리해서 하긴 했었으니.. 익숙하지 않긴 하다.