직선 좌표위에 여러개의 마을과 마을안에 여러명의 사람이 있고, 이 직선 좌표위에 우체국을 하나 놓을건데 마을 사람들의 수와 각 마을 위치를 고려해 가장 좋은 위치를 선정하는 문제이다.
마을위치 값이 -10억 ~ 10억, 각 마을의 사람 수는 0 ~ 10억으로 입력값의 범위가 매우 크다.
이 문제의 핵심은 우체국에서 각 사람까지의 거리의 합이 최소이기 위해선 특정 마을과 위치값이 같아야 한다는것이다. 따라서 모든 좌표값(20억)을 검사하는것이 아닌 각 마을의 위치(10만)만 검사하면 된다.
Sort, Greedy
각 마을들을 정렬시켜 직선 좌표 위에 올리고 우체국이 임의의 위치에 있다고 가정해보자. 이때 우체국은 어떤 마을과도 위치가 겹치지 않게 위치 시킨다. 그러면 우체국을 기준으로 왼쪽으로 총 A명의 사람들과 오른쪽으로 총 B명의 사람들이 있을것이다.
만약에 A < B라고 한다면 우체국이 오른쪽으로 한칸 이동할때마다 왼쪽의 모든 사람들로부터 한칸씩 멀어지고 오른쪽의 모든 사람들로부터 한칸씩 가까워진다. 따라서 우체국이 오른쪽으로 움직일때마다 우체국과 각 사람까지의 거리합은 A만큼 늘어나고 B만큼 줄어들기 때문에 마을이 나오기 전까지 오른쪽으로 움직이는 것이 전체 값을 더 작게 만드는 방법이 된다. A > B의 경우 반대의 방법으로 우체국을 움직이고 A = B인 경우 왼쪽과 오른쪽중 더 마을사람이 많은 마을에 우체국을 설치하면된다.
따라서 우체국이 왼쪽에서 오른쪽으로 움직이면서 전체값을 줄여나가다가 특정 마을을 지나쳤을때 다시 왼쪽으로 가야 전체값이 작아진다면 그 마을이 정답위치가 된다. 전체 마을사람들의 수는 고정되어 있으므로 A + B의 값은 고정이고 이는 가장 왼쪽 마을부터 탐색을 시작할 경우 A의 값이 절반을 넘어가는 지점의 마을을 찾으면 된다는 뜻이다.
각 마을의 위치를 정렬하는데 O(NlogN)의 시간이 걸리고 각 마을을 탐색하는데 O(N)의 시간이 걸리므로 시간복잡도는 O(NlogN)
이다. (N = 100,000)
import java.io.*;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = null;
int N;
long people_sum = 0, answer = 0;
PriorityQueue<village> queue = new PriorityQueue<>();
N = Integer.parseInt(br.readLine());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
long point, people;
point = Integer.parseInt(st.nextToken());
people = Integer.parseInt(st.nextToken());
queue.offer(new village(point, people));
people_sum += people;
}
long people_temp = 0;
for (int i = 0; i < N; i++) {
village v = queue.poll();
people_temp += v.people;
if ((people_sum + 1) / 2 <= people_temp) {
answer = v.point;
break;
}
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
}
}
class village implements Comparable<village>{
long point, people;
village(long point, long people) {
this.point = point;
this.people = people;
}
@Override
public int compareTo(village o) {
if (this.point - o.point < 0) return -1;
else if (this.point - o.point > 0) return 1;
else return 0;
}
}
좋은 풀이 잘 보고 갑니다!