Print
카테고리: [ Algorithm ]
조회수: 3966

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 &amp;&amp; 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));
  }
}