💡 풀이
var twoCitySchedCost = function (costs) {
costs.sort((a, b) => {
let diffA = a[0] - a[1];
let diffB = b[0] - b[1];
return diffB - diffA;
});
let sum = 0;
let i = 0;
let len = costs.length;
for (const [x, y] of costs) {
if (i < len / 2) sum += y;
if (i >= len / 2) sum += x;
i++;
}
return sum;
};📝 정리
처음 문제를 봤을 때, costs[i][0]과 costs[i][1] 중에 더 작은 값을 이용해 정렬을 변경해서 진행하는 줄 알았다. 조금 더 오래 고민하다, 결국 회사 입장에서는 최소가 되는 비용을 지불해야 하는 것이니, '누가 더 값이 작냐'가 문제가 아니라 '두 값의 차이'에 따라서 정렬을 해야했다.
두 값의 차이에 따라 정렬을 하면 배열의 순서가 아래와 같이 변한다.
답이 되는 최소값은 (50+20) + (10+30) = 110이 된다.
let costs = [
[400, 50],
[30, 20],
[10, 20],
[30, 200],
];그러면 앞에서부터 costs의 절반까지는 costs[i][1]의 값의 합을, 절반부터 costs 끝까지는 costs[i][0]의 값의 합을 서로 더하면 최소값을 구할 수 있다.
수정, 지적을 환영합니다!
문제 링크
https://leetcode.com/problems/two-city-scheduling/
