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

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(vector<int> picks, vector<string> minerals) {
    int answer = 0;
    int pickax[3][3] = {
        {1, 1, 1},
        {5, 1, 1},
        {25, 5, 1}
    };
    
    int totalPicks = 0;
    for(int i=0; i<picks.size(); i++){
        totalPicks += picks[i];
    }
    
    vector<vector<int>> mineralGroup;
    vector<int> group(3, 0);
    
    for(int i=0; i<minerals.size(); i++){
        if(totalPicks <= mineralGroup.size()){
            break;
        }
        
        if(minerals[i] == "diamond"){
            group[0]++;
        }else if(minerals[i] == "iron"){
            group[1]++;
        }else if(minerals[i] == "stone"){
            group[2]++;
        }
        
        if(i % 5 == 4){
            mineralGroup.push_back(group);
            group = {0, 0, 0};
        }
    }
    
    if ((group[0] > 0 || group[1] > 0 || group[2] > 0) && totalPicks > mineralGroup.size())  {
        mineralGroup.push_back(group);
    }
    
    sort(mineralGroup.begin(), mineralGroup.end(), [](const vector<int>& a, const vector<int>& b) {
        if(a[0] != b[0]){
            return a[0] > b[0];
        }
        
        if (a[1] != b[1]){
            return a[1] > b[1];
        }
        
        return a[2] > b[2];
    });
    
    int i = 0;
    int j = 0;
    
    while(i < picks.size() && j < mineralGroup.size()){
        if(picks[i] > 0){
            for(int k=0; k<3; k++){
                answer += pickax[i][k] * mineralGroup[j][k];
            }
            
            picks[i]--;
            j++;
        }else{
            i++;
        }
    }
    
    return answer;
}

---

📝 풀이

이 문제를 풀어낸 알고리즘은 다음과 같습니다.

 

1. 우선 광물들을 5개씩 묶습니다. 이 때 주의할 점은 곡괭이로 캘 수 있는 광물수까지만 묶습니다.

5개 미만인 광물들도 하나의 그룹으로 취급합니다.

2. 광물 그룹은 다이아몬드, 철, 돌 개수가 많은 순으로 내림차순 정렬을 합니다.

이렇게 하면 피로도가 많이 드는 광물을 효율적으로 캘 수 있습니다.

3. 좋은 곡괭이 순서부터 광물 그룹들을 캐며 피로도를 계산합니다.

광물을 모두 캐거나 더 이상 곡괭이가 없을 때까지 이 과정을 반복합니다.

 

최종적으로 계산된 피로도 answer을 return 합니다.