Leetcode 문제 1029번 Two City Scheduling

Leetcode 1029번 문제 Two City Scheduling

해당 문제는 Leetcode에 있는 문제입니다.

https://leetcode.com/problems/two-city-scheduling/

Two City Scheduling - LeetCode

---

문제정의

문제를 간단히 해석하자면,

한 회사는 2n명의 인터뷰 계획이 있습니다. costs[i] = [aCost_i, bCost_i]로 costs 배열이 주어지는데, 각각 i번째 사람을 a도시까지 비행하는 cost는 $ {aCost_i} $이고 b도시까지 비행하는 cost는 $bCost_i$입니다. 
각 도시에 정확히 n명 도착하도록 모든 사람을 도시로 보내주기 위해 필요한 cost의 최소값을 구하여라 

a 도시와 b 도시로 보내준 사람의 수는 각각 n으로 동일해야 하기 때문에 각 도시에 보내진 사람의 수를 세야하는 과정이 필요하며, 최소값을 구해야하기 때문에 cost끼리의 차가 큰 순서대로 정렬이 필요하다고 생각했습니다. 

---

전반적인 알고리즘

1. $a_n$, $b_n$ =  n, sum = 0
2. Quick sort, based on larger $|aCost_i - bCost_i|$. ($nlgn$)
3. loop을 돌며, 각각 sum에 추가해주고 추가된 도시의 size($a_n$ or $b_n$)를 1 감소시켜준다. ($n$)
4. 모든 과정이 끝났다면, sum을 출력해준다.

위와 같이 구현에 성공했습니다. TimeComplexity = $nlogn$

---

Code

bool compare(vector<int>& a, vector<int>& b){
    return abs(a[0] - a[1]) > abs(b[0] - b[1]) ;
}

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        int sum = 0, a_n = costs.size()/2, b_n = costs.size()/2 ;
        sort(costs.begin(), costs.end(), compare) ;
        for(vector<vector<int>>::iterator iter = costs.begin() ; iter != costs.end() ; iter++){
            if(b_n < 1 || (0 < a_n && (*iter)[0] < (*iter)[1]) || ((*iter)[0] == (*iter)[1] && b_n <= a_n)){
                // visite a
                a_n -= 1 ;
                sum += (*iter)[0] ;
            }
            else if(a_n < 1 || (0 < b_n && (*iter)[0] > (*iter)[1]) || ((*iter)[0] == (*iter)[1] && a_n <= b_n)){
                // visite b
                b_n -= 1 ;
                sum += (*iter)[1] ;
            }
        }
        return sum ;
    }
};

loop안의 조건문은 각각 다음과 같습니다.

• 다른 도시의 남은 자리가 없을 경우
• 현재 도시의 자리가 있고 $Cost_i$가 더 작을 경우
• $Cost_i$의 값이 같고 다른 도시의 size보다 현재 도시의 size가 더 크거나 같은 경우

다음과 같이 통과한 것을 볼 수 있습니다.

 

문제에 대한 코드는 Github에서도 보실 수 있습니다.

https://github.com/gurcks8989/CodingTest/blob/master/LeetCode/1029.Two_City_Scheduling.cpp

GitHub - gurcks8989/CodingTest: BackJoon_study_with_c++

훈수, 조언 언제나 환영입니다.