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

코딩테스트 연습 - 광물 캐기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
priority_queue<pair<int, int>>pq;
vector<int> new_picks;
int new_minerals[50];
int answer = 0;
string name[3] = {"diamond", "iron", "stone"};
int temp[3] = {25, 5, 1};
void make_pq(vector<string> minerals)
{
    int hap = 0, idx = 0;
    for(int i = 0; i < minerals.size(); i++)
    {
        for(int j = 0; j < 3; j++)
        {
            if(minerals[i] == name[j])
            {
                new_minerals[i] = temp[j];
                hap += temp[j];
                break;
            }
        }
        if((i + 1) % 5 == 0 || i == minerals.size() - 1)
        {
            pq.push(make_pair(hap, i / 5));
            hap = 0;
        }
    }
}

void make_new_picks(vector<int> &picks)
{
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < picks[i]; j++)
            new_picks.push_back(temp[i]);
}

void set_answer(vector<string> &minerals)
{
    int idx = 0;
    if(pq.top().second * 5 + 5 >= (minerals.size() / 5) * 5)
        if(new_picks.size() * 5 < minerals.size())
            pq.pop();
    while(!pq.empty())
    {
        if(idx >= new_picks.size())
            break;
        int max_i = pq.top().second * 5 + 5;
        if(max_i >= minerals.size()) max_i = minerals.size();
        for(int i = pq.top().second * 5 ; i < max_i; i++)
        {
            int num = new_minerals[i] / new_picks[idx];
            if(num == 0) num = 1;
            answer+= num;
        }
        pq.pop();
        idx++;
    }
}

int solution(vector<int> picks, vector<string> minerals) {
    make_new_picks(picks); //새로운 곡괭이 배열 만들기 (25,5,5,5,1,1)
    make_pq(minerals); //우선순위 큐 만들기(first: 25,5,1 / second * 5 :인덱스시작위치)
    set_answer(minerals);
    return answer;
}

코드 설명

<문제 풀이의 핵심>

캘 광물을 다이아, 철, 돌 순으로 25,5,1의 무게를 가지고 있다고 하고

곡괭이를 다이아, 철, 돌 순으로 25, 5,1의 힘을 가지고 있다고 했을 때

각각을 나누고 그 값이 0이 될때는 1로 설정해주면

이 관계를 구현해줄 수 있게 됨.

전체 minerals를 5단위로 나눠주면서 각 5단위마다 광물의 합을 더하고 이 값이 큰 순서대로 다이아-> 철-> 돌 곡괭이 순으로 뽀개주면 됨.

 

1.make_new_picks(picks)

picks는 각각 0,1,2인덱스가 다이아, 철, 돌 곡괭이의 횟수를 나타냄.

어차피 우선순위 큐 할당해주면 다이아, 철, 돌 순서대로 쓰기 때문에 쓰기 편리하게 new_picks를 이용해서 새로운 곡괭이 벡터를 만들어줌 이런식으로 (25, 5,5,5,1,1)

 

2.make_pq(minerals)

minerals 전체를 for문으로 돌면서 인덱스를 나눴을 때 5가 되거나 마지막 값이 되었을 때 지금까지 쌓아온 광물의 값을 우선순위 큐 first값으로 할당해서 넣어줌. 이 때 second값은 현재 5단위의 첫번째 인덱스 값

 

3.set_answer(minerals)

우선 문제에서 곡괭이를 다 소진했을 경우 더이상 진행하지 않는다고 했으므로,

5단위가 다 채워지지 않고 우선순위 큐의 탑이 되었을 경우 이는 처리하지 않아야 하므로 그냥 pop해줌

그렇지 않은값들은 우선순위큐가 다 빌 때까지 차례로 ineral의 마지막에 올 때까지 5단위로 광물 / 곡괭이 한 값을 answer에 더해줌