[Algorithm] Programmers :: 광물 캐기

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

프로그래머스

#define MAX_NUM 1000000
 
struct Node
{
    int index;
    int weightSum;
    int size;
    int pick = MAX_NUM;
};
 
bool weightSumDecreaseSort(const Node& a, const Node& b)
{
    return a.weightSum > b.weightSum;
}
 
bool indexIncreaseSort(const Node& a, const Node& b)
{
    return a.index < b.index;
}
 
int solution(vector<int> picks, vector<string> minerals) 
{
    int answer = 0;
    vector<Node> nodes;
    vector<int> tempPicks;
    int weights[3][3] = { {1,1,1}, {5,1,1}, {25,5,1} };
 
    for (int i = 0; i < 3; ++i)
    {
        int standard = picks[i];
 
        for (int j = 0; j < standard; ++j)
        {
            tempPicks.push_back(i);
        }
    }
    
    int mineralsSize = 0;
    int count = 0;
 
    if (tempPicks.size() >= ceil(minerals.size() / 5.0)) // 모든 광석 다 캘 수 있으면
    {
        count = minerals.size() / 5;
        mineralsSize = minerals.size();
    }
    else // 곡괭이가 부족해서 전부 못캐면, 범위내의 미네랄로만 가중치계산해야됨..
    {
        count = tempPicks.size();
        mineralsSize = count * 5;
    }
    
    int index = 0;
 
    while (1)
    {
        if (count > 0)
        {
            int weight = 0;
 
            for (int i = index; i < index + 5; ++i)
            {
                if (minerals[i] == "diamond") weight += 25;
                if (minerals[i] == "iron") weight += 5;
                if (minerals[i] == "stone") weight += 1;
            }
 
            nodes.push_back({ index,weight,5 });
            index += 5;
            --count;
 
        }
        else break;
    }
 
    if (mineralsSize % 5 != 0)
    {
        int weight = 0;
        for (int i = index; i < mineralsSize; ++i)
        {
            if (minerals[i] == "diamond") weight += 25;
            if (minerals[i] == "iron") weight += 5;
            if (minerals[i] == "stone") weight += 1;
        }
 
        nodes.push_back({ index,weight,mineralsSize - index });
    }
 
    sort(nodes.begin(), nodes.end(), weightSumDecreaseSort);
 
    for (int i = 0; i < tempPicks.size(); ++i)
    {
        if (i >= nodes.size()) // 곡괭이가 더 많을경우
        {
            break;
        }
        else
        {
            nodes[i].pick = tempPicks[i];
        }
    }
 
    sort(nodes.begin(), nodes.end(), indexIncreaseSort);
 
    for (int i = 0; i < nodes.size(); ++i)
    {
        if (nodes[i].pick == MAX_NUM) break;
 
        int curPick = nodes[i].pick;
 
        for (int j = nodes[i].index; j < nodes[i].index + nodes[i].size; ++j)
        {
            if (minerals[j] == "diamond") answer += weights[curPick][0];
            if (minerals[j] == "iron") answer += weights[curPick][1];
            if (minerals[j] == "stone") answer += weights[curPick][2];
            
        }
    }
    
    return answer;
}

n값이 작아서 완전탐색으로도 충분히 풀 수 있는 문제이긴 하지만, 만약 n값이 크게 나온다면..?

그래서 완전탐색 아닌 방식으로 푸는쪽으로 생각해봤다.

 

큰 틀은 광석을 5개씩 나눠서 가중치를 계산해서 정렬해서 어떤 곡괭이를 쓸지 계산하는 것이다.

즉, 0번째 인덱스부터 4번째 인덱스까지의 5개의 광석의 가중치값(피로도값)이 가장 크다면, 거기는 다이아곡괭이로 작업을 하는게 가장 적은 피로도를 소모할 것이다.

이렇게 최대 5개씩 나눠서 node로 보관한다. node에는 시작index(index), 광석갯수(size), 가중치합(weightSum), 곡괭이타입(pick) 의 멤버변수가 있다.

 

즉, 시작인덱스에서 시작인덱스 + size 까지의 가중치합을 구한다음, node를 가중치합을 기준으로 정렬을 시키고 가중치합이 큰 순서대로 node의 pick에다가 가장 좋은 곡괭이를 하나씩 넣는 방식이다.

 

그다음 다시 index기준으로 오름차순정렬을 해준다음 앞에서부터 pick에 담겨있는 곡괭이로 피로도를 계산해주면 된다.

 

주의할 점은, 광석을 캐는데 필요한 곡괭이가 부족할 수도 있다는 것이다.

즉 광석은 총 13개인데 곡괭이를 1개만 줄 수도 있다. 그리고 그 반대일 수도 있고.

이 점을 명심해서 코드를 작성하면 된다.