1029. Two City Scheduling
💡 풀이
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/
LeetCode GitHub
https://github.com/tTab1204/LeetCode
Author And Source
이 문제에 관하여(1029. Two City Scheduling), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ken1204/1029.-Two-City-Scheduling저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)