Leetcode - 1029. Two City Scheduling

1. 문제

💡 A company is planning to interview 2n people. Given the array costs where costs[i] = [aCosti, bCosti], the cost of flying the ith person to city a is aCosti, and the cost of flying the ith person to city b is bCosti.

Return the minimum cost to fly every person to a city such that exactly n people arrive in each city.

• 2n명의 사람을 인터뷰 해야하는데 각 사람이 A도시, B도시로 가는데 필요한 비용(cost)이 배열로 주어진다.
• 모든 사람을 각각의 도시로 보낼 때 필요한 최소 비용을 구하라.
• 만약 4명이라면 2명은 A도시, 2명은 B도시로 보내야 한다.

• 2 <= costs.length <= 100
• costs.length is even.

2. 잘못된 첫 번째 접근법

우선 costs의 길이가 100까지니까 Brute Force로 모든 경우의 수를 구하여 풀어도 될까? 라는 생각이 들었다. 주어진 costs 배열을 순회하면서 A도시로 갔을 때, B도시로 갔을 때로 나눠서 모든 경우를 살펴보는 것이다.

다만, 이 경우는 단점이 명확하다. 모든 경우를 살펴보기 때문에 정답은 정확하게 찾아낼 수 있지만 시간 복잡도는 O($2^n$)이기 때문에 만약 배열의 길이가 100이라면..? 1.2676506002282294e+30 가지를 살펴봐야 한다.. 숫자 읽기도 힘들어진다.

3. 두 번째 접근법

그럼 두 도시로 가는 비용의 차이를 통해서 각 도시로 가는 비용의 가중치를 볼 수 있을까? 로 접근했다. 만약 costs = [[10,20],[30,200],[400,50],[30,20]] 일 때 B도시 비용 - A도시 비용 의 값을 구해보면 [10, 170, -350, -10] 이다. 이 값이 의미하는 것은 값이 클 수록 B도시로 가는 상대 비용이 큰 것이고, 값이 작을수록 B도시로 가는 상대 비용이 작은 것이다.

이를 오름차순으로 정렬하면 다음과 같다.

값이 작을수록 A도시로 가는 것보다 B도시로 가는 것이 좋다. B도시 비용과 A도시 비용의 차이를 기준으로 선택하기 때문에 절대적인 비용에서 차이가 있더라도 전체 비용은 최소 비용이 될 수 있는 것이다.

이 경우의 전체 시간 복잡도는 O($nlogn$)이다. 각각의 차이를 구하는 것, 전체 Cost를 구하는 것 모두 O(n)이고, 오름차순 정렬에 O($nlogn$)이 필요하기 때문이다. 위에서 접근한 Brute Force에 비해 시간 복잡도가 확 낮아졌다.

4. 정답 코드

function twoCitySchedCost(costs) {
  return costs
    .map(cost => cost.concat(cost[1] - cost[0]))
    .sort((a, b) => a[2] - b[2])
    .reduce((acc, cur, i) => {
      if (i < costs.length / 2) {
        return acc + cur[1];
      } else {
        return acc + cur[0];
      }
    }, 0);
};

고차 함수를 체이닝해서 작성해봤는데 순서대로

1. map을 통해 각 요소를 순회하면서 B도시 비용 - A도시 비용 값을 요소에 추가한다.
2. 각 요소의 추가된 B도시 비용 - A도시 비용 비용의 차이를 기준으로 오름차순 정렬한다.
3. 절반은 A도시, 절반은 B도시로 보내야 하므로 index를 기준으로 costs.length / 2 보다 작으면 B도시, 보다 크면 A도시로 가는 비용을 더한다.

를 의미한다.