1. 문제
출처 : https://programmers.co.kr/learn/challenge_codes/184
1보다 큰 N개의 도시 중 한 곳에 공항을 지을 예정입니다. 사람들의 편의를 위해 공항으로부터 각 사람들까지의 도시간 이동 거리가 최소가 되는 도시에 짓기로 하였습니다. 편의상 도시는 일직선상에 놓여있다고 가정하며 좌표의 범위는 음수가 포함됩니다. 또한 좌표는 정렬되어 있지 않습니다. 직선상의 위치와 그 도시에 사는 사람들의 수가 주어질 때, 공항을 지을 도시의 위치를 반환해주는 함수 chooseCity 함수를 완성하세요. 거리가 같은 도시가 2개 이상일 경우 위치가 더 작은 쪽의 도시를 선택하면 됩니다. 예를 들어 다음과 같은 정보의 도시가 있다고 가정해 봅시다.
위치 | 1 | 2 | 3 |
---|---|---|---|
인구수 | 5 | 2 | 3 |
이 살 경우, 각각의 도시에 공항을 지었을 때의 사람들의 이동 거리는 8, 8, 12 이므로 1번 또는 2번에 지을 수 있지만, 1의 위치가 더 작으므로 1을 반환해주면 됩니다.
2. 코드
아래 코드로는 오류가 발생하거나 타임아웃이 발생하였음. 더 좋은 코드가 있으면 공유하시기 바랍니다.
public class AirportConstruction { public int chooseCity(int n, int[][] city) { int answer = 0; int distance = 0; int minLocation = 0; for ( int inx = 0; inx < n; inx++ ) { int pivot = city[inx][0]; int dist = 0; for ( int jnx = 0; jnx < n; jnx++ ) { if ( inx != jnx ) { dist += (Math.abs(city[jnx][0] - pivot) * city[jnx][1]); } } if ( inx == 0 || dist < distance || (dist == distance && pivot < minLocation) ) { answer = pivot; minLocation = answer; distance = dist; } } return answer; } public static void main(String[] args) { AirportConstruction ac = new AirportConstruction(); int tn = 4; int[][] tcity = { { 1, 5 }, { 2, 2 }, { 3, 3 } }; System.out.println(ac.chooseCity(tn, tcity)); } }