[LeetCode] 1029.Two City Scheduling

여기를 클릭하면 문제를 볼 수 있습니다.

📕 문제 설명

한 회사가 2n명의 사람을 인터뷰 하고자 한다.
한 사람당 a city로 이동하는 비용을 aCost, b city로 이동하는 비용을 bCost라 하여 이동 비용에 대한 정보가 costs 배열로 주어졌을 때 2n명의 사람을 a city와 b city로 n명씩 이동하게 하되 그 cost의 총합이 최소가 되게 해야 한다.

위의 Example 1을 통해 설명을 추가하자면
4명의 사람이 주어졌기 때문에 a city와 b city에 2명씩 분배되어야 한다. 이때 최소가 되게하는 cost들의 합은

• 1번째 사람을 a city로 (cost = 10)
• 2번째 사람을 a city로 (cost = 10)
• 3번째 사람을 b city로 (cost = 50)
• 4번째 사람을 b city로 (cost = 20)

와 같이 하여 총 합은 10+30+50+20=110 이 최소 cost가 된다.

📕 문제 풀이

만약 문제에 a city 와 b city에 n명씩 분배하라는 조건이 없었으면 각 사람마다 비용이 더 적은 도시로 이동을 시키면 된다.

하지만 이 문제의 경우 n명씩 분배하라는 조건이 있으므로 어느 한 도시로의 이동 비용을 기준으로 잡고 정렬하여 풀면 오류가 발생한다.

예를 들어 cost = [[10,20],[20,30],[30,200],[40,500]] 으로 주어졌다고 하자.
a city로의 이동 비용을 기준으로 정렬하여 풀면 cost의 합이 10+20 (a에 n명이 분배되었으므로 나머지는 b)+200+500=730 이 되므로 최소 비용인 20+30+30+40=120이 나오지 않는다. 그러니 한 도시의 비용을 기준으로 잡고 정렬해서는 풀릴 문제가 아니다.

문제를 다른 방향으로 접근해보자. 위의 예를 다시 생각해보면 비용이 큰 것을 피해서 고르다 보면 최소 cost가 될 것이다. 즉, [40,500],[30,200],[20,30],[10,20] 으로 정렬하여 큰 것을 피해서 고르면 40+30+30+20=120이 되어 최소 cost를 알 수 있다. 그런데 비용이 큰 것은 aCost와 bCost에 모두 존재할 수 있으므로 어느 하나를 기준으로 정렬하는 것이 아니라 둘을 관계지어 정렬해야 한다.

그러므로 |aCost-bCost|를 계산하여 이 값이 큰 것부터 정렬하여 각 단계마다 적은 것들을 고르다 보면 최소 cost에 도달되어 있을 것이다.

cost = [[30,100],[60,10],[10,50],[100,450]] 이 주어졌다고 하자. |aCost-bCost|를 기준으로 큰 것부터 정렬을 하면 [100,450],[30,100],[60,10],[10,50]]이 된다. 여기서 각 단계마다 적은 것을 선택하면 100+30+10+50=190이 되어 최소 cost를 얻을 수 있다.
이제 이것을 코드로 나타내보자.

📕 Code

typedef struct cost
{
    int aCost;
    int bCost;
} cost;    // cost 정보가 담긴 구조체

int compare(cost a, cost b)
{
    return abs(a.aCost-a.bCost) > abs(b.aCost-b.bCost);
}   // |aCost-bCost| 큰 순으로 정렬

class Solution 
{
public:
    int twoCitySchedCost(vector<vector<int>>& costs) 
    {
        vector<cost> nCosts;
        int len = costs.size();
        for(int i=0; i<len; i++)
        {
            cost tmp;
            tmp.aCost = costs[i][0];
            tmp.bCost = costs[i][1];
            nCosts.push_back(tmp);
        }
        
        sort(nCosts.begin(), nCosts.end(), compare);
        
        int ans = 0, an=0, bn=0;
        for(int i=0; i<len; i++)
        {
            if(an == len/2)      // a에 n명이 분배 되었다면
            {
                ans += nCosts[i].bCost;   // b city만
                bn++;
            }
            else if(bn == len/2)   // b에 n명이 분배되었다면
            {
                ans += nCosts[i].aCost;   // a만
                an++;
            }
            else   // 아직 n명씩 덜 분배되었다면
            {
                if(nCosts[i].aCost < nCosts[i].bCost) // 더 작은 비용의 도시를 선택   
                {
                    ans += nCosts[i].aCost;
                    an++;
                }
                else
                {
                    ans += nCosts[i].bCost;
                    bn++;
                }
            }
        }
        
        return ans;
    }
};

📕 후기

정렬의 기준을 생각하는 데에 시간이 좀 걸렸다. 정렬 기준을 찾고 나서도 왜 그게 정렬기준이 되는지 정확히 설명하기 어려웠다. 그래도 혼자 힘으로 greedy algorithm 문제를 풀어 기뻤다.