[Level2.] 광물 캐기 C++

<< 문제 >>

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

프로그래머스

 

미네랄 벡터를 한 세트당 최대 다섯개로 묶었습니다.

 

세트 별로 다이아몬드, 철, 돌로 Priority Queue를 이용해 내림차순 정렬하여,

 

가장 먼저 나오는 세트부터 높은 곡괭이를 부여했습니다.

 

 

여기서 실수하기 쉬운 것은... 곡괭이 수를 넘어서는 미네랄들은 터치할 수 없다는 것입니다. 

 

아예 고려할 필요가 없는 것이죠.

 

그걸 생각 안하고 풀었다가 8번 케이스만 통과 못해서 고민을 좀 했습니다. 

 

 

<< 코드 >>

#include <string>
#include <vector>
#include <queue>

using namespace std;

// 곡괭이와 미네랄 셋을 입력받아 한 세트의 피로도 계산
int calc(int pick, vector<int> mineral){ 
    int result = 0; 
    
    if(pick == 0){
        result += mineral[0];
        result += mineral[1];
        result += mineral[2];
    }
    else if(pick == 1){
        result += mineral[0] * 5;
        result += mineral[1];
        result += mineral[2];
    }
    else if(pick == 2){
        result += mineral[0] * 25;
        result += mineral[1] * 5;
        result += mineral[2];
    }
    return result;
}

// 5개씩 {다이아, 철, 돌} 를 해서 정렬해서 다이아 많은 것 부터 다이아 곡괭이 쓰면 될 듯  
int solution(vector<int> picks, vector<string> minerals) {
    int answer = 0;
    
    // 곡괭이의 수.. 곡괭이를 앞에서부터 쓰니까 곡괭이 수를 넘어서는 광물은 고려대상이 아님.
    int pickNum = 0;
    for(auto& p :picks){
        pickNum += p;
    }
    
    priority_queue<vector<int>> pq;
    queue<string> q;
    
    // 순차적으로 꺼내기 위해 q사용
    for(auto& a : minerals){
        q.push(a);
    }
    
    // 캘 수 있는 광물 중 다이아 곡괭이에 대한 우선순위 부여
    for(int i = 0; i < pickNum; i++){
        vector<int> newVec = {0,0,0};
        for(int j=0; j<5; j++){
            if(q.front() == "diamond"){
                newVec[0]++;
            }
            else if(q.front() == "iron"){
                newVec[1]++;
            } 
            else if(q.front() == "stone"){
                newVec[2]++;
            }
            q.pop();
            if(q.empty()){
                break;
            }
        }
        pq.push(newVec);
        if(q.empty()){
                break;
        }
    }

    // 곡괭이와 미네랄 세트를 입력
    while(!pq.empty()){
        int pick;

        if(picks[0] > 0){
            pick = 0;
            picks[0]--;
        }
        else if(picks[1] > 0){
            pick = 1;
            picks[1]--;
        }
        else if(picks[2] > 0){
            pick = 2;
            picks[2]--;
        }
        else{
            break;
        }
        answer += calc(pick, pq.top());
        pq.pop();
    }
    
    
    return answer;
}

 

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/172927.%20%EA%B4%91%EB%AC%BC%20%EC%BA%90%EA%B8%B0