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