[프로그래머스 4단계] 알고리즘 35. 공항 건설하기

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 35. 공항 건설하기

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

위치	1	2	3
인구수	5	2	3

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

풀이:

나의 알고리즘은 다음과 같다.

1. 위치를 기준으로 정렬한다.

2. 중간을 기준으로 왼/오른쪽에 있는 인구수가 절반이 되는 지점을 찾는다.

이 문제의 핵심은 최적의 이동거리를 만들어내는 지점은 중간을 기준으로 제일 가까운 위치에서 인구수가 절반이 되는 지점이라는 것이다. 따라서 나의 코드는 다음과 같다.

int chooseCity(int n, vector<pair<int,int>> city)

{

int answer = city[0].first;

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

long long left = 0,

right = accumulate(city.begin(),

city.end(),

0L,

[](long long res, pair<int, int> c){

return res += c.second;

});

for (int i=0; i<n-1; i++)

{

 left += city[i].second;

right -= city[i].second;

if (right > left)

answer = city[i+1].first;

}

    return answer;

}

left(초기값: 0), right(초기값: 현재 인구수 총합)는 왼쪽 오른쪽 지점의 인구 분포를 나타낸다. 주의할 점은 accumulate 함수에서 초기값을 0L로 해두어야 long long 계산을 정확하게 수행한다. 이제 왼쪽에서부터 인구수를 더하고 오른쪽에서부터 인구수를 뺀다. 그리고 오른쪽이 왼쪽보다 크다면 자기보다 한 칸 앞선 지점의 위치를 저장해두면 된다. 사실 이 문제를 2시간 내내 풀다가 못 풀어서 다른 사람의 파이썬 코드를 보았다. 그런데 이해가 잘 안간다;;; 무슨 이론을 토대로 푼 것 같은데..