공항 건설하기

문제

1보다 큰 N개의 도시 중 한 곳에 공항을 지을 예정입니다. 사람들의 편의를 위해 공항으로부터 각 사람들까지의 도시간 이동 거리가 최소가 되는 도시에 짓기로 하였습니다. 편의상 도시는 일직선상에 놓여있다고 가정하며 좌표의 범위는 음수가 포함됩니다. 또한 좌표는 정렬되어 있지 않습니다. 직선상의 위치와 그 도시에 사는 사람들의 수가 주어질 때, 공항을 지을 도시의 위치를 반환해주는 함수 chooseCity 함수를 완성하세요. 거리가 같은 도시가 2개 이상일 경우 위치가 더 작은 쪽의 도시를 선택하면 됩니다. 예를 들어 다음과 같은 정보의 도시가 있다고 가정해 봅시다.

위치	1	2	3
인구수	5	2	3

이 살 경우, 각각의 도시에 공항을 지었을 때의 사람들의 이동 거리는 8, 8, 12 이므로 1번 또는 2번에 지을 수 있지만, 1의 위치가 더 작으므로 1을 반환해주면 됩니다.

풀이

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int chooseCity(int n, vector<pair<int, int>> city)
{
  int      answer = 0, i;
  __int128 sum    = 0, half;

  sort(city.begin(), city.end());

  for (i = 0; i < n; i++) sum += city[i].second;
  half = sum / 2;
  if (half * 2 != sum)
    half++;

  for (i = 0, sum = 0; i < n; i++)
  {
    sum += city[i].second;
    if (sum >= half)
      break;
  }
  return city[i].first;
}

int main()
{
  int            tn = 3;
  pair<int, int> a, b, c;
  a.first = 1, a.second = 5;
  b.first = 2, b.second = 2;
  c.first = 3, c.second = 3;
  vector<pair<int, int>> tcity{ a, b, c };

  // 아래는 테스트 출력을 위한 코드입니다.
  cout << chooseCity(tn, tcity);
}

일단 제출해보고 테스트 케이스를 보면 답도 안나온다.

범위가 정해지지도 않아 원초적으로 접근할 경우 아마 대부분 시간 초과가 뜰 것이다.
(실제로 제출된 코드들도 시간 초과 코드가 대부분.. 이상하게도 시간초과로 실패했는데 제출은 되는 것 같다;;)

접근 방법을 다르게 하여 생각해보았다.
(수학적 증명은 패스.. 사실 모르겠어요..단순하게 생각만..)

공항을 지을 때 어디에 지어야 될까? 내 생각에는 사람이 많은 곳에 지어야 한다.

따라서 먼저 좌표(위치)를 기준으로 오름차순 정렬한다.

그럼 -3, -2, -1, 0, 1, 2, 3, .. 순으로 변환되고 만약 중간 중간의 좌표가 존재하지 않는다 하면 그 좌표 값(인구수)은 0으로 되어 있다고 생각만 하자.

그럼 각 좌표는 모두 1 단위씩 (머리속에) 생길거고 이제 맨 좌측 값부터 사람 수를 더해간다.

더하다가 인구 수의 50%가 되는 지점. 즉 미리 구해놓은 전체 인구수의 절반 값에 해당하는 지점에 공항을 건설하는 것으로 생각하였다.

테스트 케이스를 보면 값이 말도 안되게 크게 나와 __int128형 또는 long long형을 통해 값을 컨트롤해야 할 것이다.

출처

알고리즘 연습 Level 4 | 프로그래머스