LeetCode : : 1029번 Two City Scheduling - C++ 풀이

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

Two City Scheduling - LeetCode

 

class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) {
        int len = costs.size();
        int total = 0;
        int countA = 0;
        int countB = 0;
        
        for(int i = 0; i < len; i++){
            costs[i].insert(costs[i].begin(),abs(costs[i][0]-costs[i][1]));
        }
        
        sort(costs.begin(), costs.end());
        
        for(int i = (len-1); i >= 0; i--){
          
                
                if(countA == len/2){
                    total = total+costs[i][2];
                    continue;
                }
                else if(countB == len/2){
                    total = total+costs[i][1];
                    continue;
                }
                
                if(costs[i][1] <= costs[i][2]){ 
                    total = total+costs[i][1];
                    countA++;
                }
                else if(costs[i][1] > costs[i][2]){ 
                    total = total+costs[i][2];
                    countB++;
                } 
 
        }  
        return total;
    }
 
};

문제 풀이

코드 설명

절댓값을 기준으로 sorting 해야하는데,

cost 차의 절댓값을 위한 vector나 array를 따로 만들고, 그것을 sorting해주고 또 그 순서에 맞게 costs 벡터를 다시 sort해주는 게 번거로울 것 같아서

costs 벡터에 절댓값을 추가해주었다.

 

예를 들면,

(840, 118)의 경우 두 cost 차의 절댓값은 722

(840, 118)에 722를 추가하여 (722, 840, 118)로 만든다.

 

이런식으로 벡터에 값을 추가하고 sorting을 해주면 첫번째 원소 값 기준으로 sorting이 진행된다. 

즉, 아래 그림처럼 벡터값들이 정렬된다. 

 

 

vector에 v.push_back()은 있지만 v.push_front()는 없기때문에 !!! insert 함수를 항상 기억하자
문제를 잘 읽어보자ㅠㅠ 처음에는 greedy 문제인지 몰랐다ㅠㅠ

 

greedy 알고리즘 공부할때 참조할 블로그 

https://blog.naver.com/ndb796/221242106787

34. 그리디(Greedy) 알고리즘