[Heap/Priority Queue][Medium] 2462. Total Cost to Hire K Workers

https://leetcode.com/problems/total-cost-to-hire-k-workers/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. k수의 worker를 고용한다고 할때, costs는 각 worker의 비용이다.
 아래와 같은 규칙으로 worker를 고용한다고 할때, k회의 세션 이후 최종 고용비용을 반환하라.
 - 총 k 세션을 돌면서 각 세션당 1명씩 고용하며, 고용된 노동자는 리스트에서 제거된다.
 - 목록의 앞에서 candidates만큼 후보군을 정하고, 뒤로도 해당 후보군을 정한다.
 - 위 두 후보군 중에 최소비용의 노동자를 고용한다.
 - 후보군보다 적은 수의 노동자만이 있다면, 그 중에서 최소비용의 노동자를 고용한다.

 

 

Solution. 

 복잡해 보인다. 

 늘 느끼지만, leetcode는 영어 site므로, 언제나 문제의 1차 해석이 중요하다. 

 시간을 두고, 먼저 문제 자체를 이해 하자. 

 

 리스트의 앞과 뒤를 cadidates만큼 덜어 놓고, 전체 그 중에 가장 작은 녀석을 k 세션동안 찾고, 합을 구하는 문제이다. 

 

 고용, 세션 이런걸 제외하고 문제자체로만 보면 간단하다. 

 

 우선, 리스트의 전반부, 후반부의 선택 부분을 저장할 버퍼가 필요하다. 

 이 녀석들 중 최소를 찾아 더하면 되므로, 

 매번 이녀석을 정렬하여 찾으면 될 것이다. 

 하지만, 우선순위 큐를 쓰면, insert 연산시에 이미 최소(최대)값이 top 에 위치되므로, 이를 이용한다. 

 

 따라서 최소값을 반환하고(고용하고), 이 값을 큐에서 제외하고, 새로운 대상을 insert 한다.  

 이 과정을 session 수 만큼 하고, 총 합을 반환한다. 

 

 좀 간단해 진것 같다. 

 로직을 코드로 써 본다. 

 

long long totalCost(vector<int>& costs, int k, int candidates) 
{
    vector<bool> vHired;
    vHired.resize(costs.size(), false);

    priority_queue<pair<int, pair<int, bool>>, vector<pair<int, pair<int, bool>>>, greater<pair<int, pair<int, bool>>> > qBuff;
    // value, (index, IsDirectionTail)

    int idxHead = 0;
    int idxTail = costs.size() - 1;
    int cntHead = 0, cntTail = 0;
    // 우선 전체 costs중에 앞 뒤로 cadidates만큼 push한다.
    for (int q = 0; q < costs.size(); ++q)
    {
        if (cntHead < candidates)
        {
            qBuff.push(make_pair(costs[q], make_pair(q, true)));
            idxHead = q;
            ++cntHead;
            if(qBuff.size() >= costs.size())   
                break;
        }

        int idxBack = costs.size() - q - 1;
        if (cntTail < candidates)
        {
            qBuff.push(make_pair(costs[idxBack], make_pair(idxBack, false)));
            idxTail = idxBack;
            ++cntTail;
            if(qBuff.size() >= costs.size())   
                break;
        }
        // 모두 다 push 하였다면, 더 이상 할 필요 없다.
        if (cntHead >= candidates && cntTail >= candidates)
            break;
    }

    long long total = 0;
    for (int q = 0; q < k; ++q)
    {
        total += ((long long)qBuff.top().first);
        // 고용된 index를 flag 처리 한다.
        vHired[ qBuff.top().second.first ] = true;
        // 앞과 뒤로 향하는 방향을 알 필요가 있다.
        bool isDirBack = qBuff.top().second.second;
        qBuff.pop();

        if(idxHead+1 >= idxTail)   continue;

        // 각 방향에 맞게 다음 원소를 push 한다.
        if(isDirBack)
        {
            ++idxHead;
            while(idxHead<costs.size() && vHired[idxHead])
                idxHead++;
            if(idxHead < costs.size())
                qBuff.push(make_pair(costs[idxHead], make_pair(idxHead, true)));
        }
        else
        {
            --idxTail;
            while(idxTail>=0 && vHired[idxTail])
                idxTail--;
            if(idxTail >= 0)
                qBuff.push(make_pair(costs[idxTail], make_pair(idxTail, false)));
        }
    }
    return total;
}

 

만족스럽진 않지만, 어쨌든 accepted가 뜨긴 했다.

 

Note ) 먼저, 이 문제는 문제 해석을 잘못하여 여러날을 소비했다. 해석이 정말 중요하다. 

 둘째로 이 문제는 priority queue 자체 뿐이 아니라도, 여러 요소를 세심히 고려하여야 풀리는 문제다. 

 우선 변수나 buffer를 많이 쓰더라도 직관적으로 가독성있는 코드를 만들고, 그 다음에 로직 최적화를 권한다.