leetcode_Two City Scheduling

 

오늘은 leetcode의 Two City Scheduling을 풀어보았다.

 

There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].

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

input : [[10,20],[30,200],[400,50],[30,20]]
outpupt : 110

인터뷰를 위해 회사로 가야하는 사람이 2N명 있다.

i번째 사람이,

A 도시로 가는 비용은 costs[i][0] 이고

B 도시로 가는 비용은 costs[i][1] 이다.

 

두 도시에 각 N명씩, 모든 사람이 도시에 도착해야하고, 그때 발생하는 최소 비용을 구하라.

 

---

고려해야하는 부분은 이렇게 정리할 수 있다.

1. A와 B 도시 각각 N명씩 도착해야 한다.

2. 발생하는 비용을 최소화 해야 한다.

 

만약 모든 사람이 도착하기 전에,

이미 A 도시에 도착한 사람이 N명으로 꽉 찬 경우,

남은 사람들은 A 도시로 향하는 비용이 더 적다고 할지라도,

A 도시에 이미 N명의 사람이 도착했기 때문에 나머지는 B 도시로 이동해야한다!

 

A 도시	B 도시
10	30
20	40
30	50
40	60
2명	2명

2번째 사람까지는 최소비용을 따져서 비용이 적게 드는 쪽(A 도시)으로 이동했다.

3번째 사람 역시 A 도시로 가는 비용이 더 적지만 

이미 A 도시에는 모든 인원( 2N )의 절반( N )인 2명의 사람이 이동해 있는 상태이기 때문에, B 도시로 이동해야한다.

 

여기서 생각해 볼 수 있는 것은,

점점 뒤로 갈수록 최소비용이 아닌 선택을 할 가능성이 커진다는 점.

최대의 이익을 볼 수 있는 선택을 해야되기 때문에,

기왕이면 비록 최소비용이 아닌 선택을 하더라도 그에 대한 타격이 상대적으로 적은 선택을 하는 것이 좋겠다.

 

이것이 무슨 말인가 하면, 아래 표를 살펴보자.

 

**input = [[10,20], [30,50], [40,70], [50,100]]

A 도시	B 도시	A 도시	B 도시
10	20	50	100
30	50	40	70
40	70	30	50
50	100	10	20
총 비용	10+30+70+100 = 210	총 비용	50+40+50+20 160

두 케이스는 모두 input 값으로 같은 데이터를 받았지만, 총 비용을 확인해보면 큰 차이가 있다.

왼쪽은 받은 input 값을 그대로 사용했고, 오른쪽은 input 값을 어떠한 기준으로 정렬한 뒤 사용했기 때문이다.

 

오른쪽의 경우 A와 B 비용의 차이의 절대값( | a - b | )을 기준으로 내림차순 정렬을 했다.

 

이렇게 되면

각 도시에 N명이 배정되기 전까지는 최소비용으로 최선의 선택을 할 수 있고,

최소비용을 선택할 수 없더라도, 두 비용의 차이가 적은, 상대적으로  손실이 적은 선택을 할 수 있게 된다.

 

 

+ Array custom sort 

array.sort( compareFunction );

compareFunction(a, b) < 0 의 경우, a가 먼저 (a의 색인이 b보다 낮다.)

compareFunction(a, b) > 0 의 경우, b가 먼저 (b의 색인이 a보다 낮다.)

compareFunction(a, b) = 0 의 경우, 그대로 (변경없음)

  costs.sort( function (a,b) {
    //[A city , B city]
    //a : [10, 20]
    //b : [40, 70]
    return Math.abs((b[0]-b[1]))-Math.abs((a[0]-a[1]));
  	// (| 40 - 70 |) - (| 10 - 20|)
  });
  //각 도시의 비용 차이를 절대값으로 바꾸어 내림차순으로 정렬

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

Array.prototype.sort()