[프로그래머스 C#] Lv.2 광물 캐기

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

하나의 곡괭이로 무조건 5개의 광물을 연속으로 캐야 하므로, 연속된 5개의 광물을 그룹으로 묶어서 비용이 많이 드는 그룹부터 가장 높은 등급의 곡괭이로 캐야 하는 문제

 

- 연속으로 캐야하는 광물 그룹을 주어진 곡괭이들로 캘 경우의 피로도를 담은 데이터클래스 GroupCostData

- [곡괭이, 광물] 에 cost 값을 가지는 2차원 배열을 활용 ( costArrays )

 -> 광석들은 string 배열로 되어 있으므로, 더 편하게 사용하기 위해 int형 배열에 따로 담음

 

1) 연속된 5개의 광물을 데이터클래스 형식에 맞춰 list에 담음

- 5개가 되지 않아도 남은 광석이 없다면 담아야 함

주의) 곡괭이가 부족할 경우 캘 수 없는 광석이므로 리스트에 담아선 안됨

 

2) 데이터 클래스 내의 모든 피로도를 합친 값을 기준으로 내림차순 정렬함

- 가장 피로도가 많이 들 수 있는 광석을 좋은 곡괭이로 캐야 하므로 데이터 클래스 내의 피로도의 총합을 기준으로 함

+ 비교 우선순위를 stoneCost -> ironCost -> diamondCost로 비교하는 것과 동일 ( 주어진 조건에 의해 )

 

3) 정렬된 리스트에 순서대로 접근하며 가장 높은 등급의 곡괭이로 캠

- 피로도 총합에 따라 내림차순 정렬되어 있기 때문에 0번 인덱스부터 순차적으로 캐나가면 됨

 

+ 주어진 광석의 개수가 50개 이하이므로 DFS로 풀이할 수도 있음

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

 

주석 참조

    using System;
    using System.Collections.Generic;

    public class Solution
    {
        // 각 그룹을 주어진 곡괭이로 캤을 때의 피로도를 담은 데이터 클래스
        public class GroupCostData
        {
            public int diamondCost;
            public int ironCost;
            public int stoneCost;

            public GroupCostData(int diamondCost, int ironCost, int stoneCost)
            {
                this.diamondCost = diamondCost;
                this.ironCost = ironCost;
                this.stoneCost = stoneCost;
            }
        }

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

            var groupCostDataList = new List<GroupCostData>(); // 피로도 데이터 클래스 리스트
            var costArrays = new int[3, 3] // [곡괭이, 광물] 에 따른 cost 값을 담은 2차원 배열
            {
                {1, 1, 1},
                {5, 1, 1},
                {25, 5, 1}
            };

            // 광석 string 배열 -> int 배열 (costArrays를 편하게 사용하기 위해)
            var mineralsIndex = new int[minerals.Length];
            for (int i = 0; i < minerals.Length; i++)
            {
                switch (minerals[i])
                {
                    case "diamond": mineralsIndex[i] = 0; break;
                    case "iron": mineralsIndex[i] = 1; break;
                    case "stone": mineralsIndex[i] = 2; break;
                }
            }

            int index = 0;
            int picksCount = picks[0] + picks[1] + picks[2];

            // 1) 연속된 5개의 광석을 묶어서 List에 담음
            while (picksCount > 0)
            {
                int diamondCost = 0;
                int ironCost = 0;
                int stoneCost = 0;

                for (int i = 0; i < 5; i++)
                {
                    // 만약 모든 광석을 다 캤다면
                    if (index + i >= mineralsIndex.Length)
                        break;

                    diamondCost += costArrays[0, mineralsIndex[index + i]];
                    ironCost += costArrays[1, mineralsIndex[index + i]];
                    stoneCost += costArrays[2, mineralsIndex[index + i]];
                }

                picksCount--;
                index += 5;
                groupCostDataList.Add(new GroupCostData(diamondCost, ironCost, stoneCost));
            }

            // 2) 모든 코스트의 합을 기준으로 내림차순 정렬
            groupCostDataList.Sort((x, y) => CompareTo(x, y));

            // 3) 가장 큰 값부터 다이아 -> 철 -> 돌 곡괭이로 캠
            for (int i = 0; i < groupCostDataList.Count; i++)
            {
                if (picks[0] > 0)
                {
                    picks[0]--;
                    answer += groupCostDataList[i].diamondCost;
                }
                else if (picks[1] > 0)
                {
                    picks[1]--;
                    answer += groupCostDataList[i].ironCost;
                }
                else if (picks[2] > 0)
                {
                    picks[2]--;
                    answer += groupCostDataList[i].stoneCost;
                }
            }

            return answer;
        }

        // 데이터 클래스를 코스트 값에 따라 내림차순 정렬하기 위한 메서드
        public int CompareTo(GroupCostData data1, GroupCostData data2)
        {
            int total1 = data1.diamondCost + data1.ironCost + data1.stoneCost;
            int total2 = data2.diamondCost + data2.ironCost + data2.stoneCost;
            return total1 > total2 ? -1 : 1;
        }
    }