[Leetcode] 1029. Two City Scheduling

 

Two City Scheduling - LeetCode

 

다해봐도 모르겠어서 가능한 모든 경우의 수를 찾아서 최소값을 구하는 방법을 생각해봤는데

이는 O(n⁴) 까지 고려해야 한다.

 

Main Idea를 찾아본 결과

a와 b의 차이가 가장 큰 경우 작은 값을 이용하면 됐다.

은근 단순해서 화났음

/*
1. costs의 a와 b의 차이와 index를 2차원 배열에 저장
2. gap 값을 기준으로 오름차순 정렬
3. costs size까지 반복하며 순서대로 a,b costs size 절반을 넘지 않도록 더함 
*/


class Solution {
public:
    int twoCitySchedCost(vector<vector<int>>& costs) 
    {
        vector<vector<int>> gap_index;
        int a = 0;
        int b = 0;
        int ans = 0;
        for(int i=0; i<costs.size(); i++) //1과정
        {
            vector<int> v;
            v.push_back(abs(costs[i][0] - costs[i][1]));
            v.push_back(i);
            
            gap_index.push_back(v);           
        }
        
        sort(gap_index.begin(), gap_index.end(), greater<>()); //2과정
        
        
        for(int i=0; i<costs.size(); i++) //3과정
        {
            int idx = gap_index[i][1];
            
            if((costs[idx][0] < costs[idx][1] && a<costs.size()/2) || b>= costs.size()/2) 
            {
                ans += costs[idx][0];
                a++;
            }
            else if((costs[idx][0] >= costs[idx][1] && b<costs.size()/2) || a>= costs.size()/2) 
            {
                ans += costs[idx][1];
                b++;                
            } 
        }    
        
        return ans;
    }
};

실수..

a, b 차이를 내림차순으로 indexing 해야되는데 오름차순해버림 ㅋㅋ;