문제해설

직선 좌표위에 여러개의 마을과 마을안에 여러명의 사람이 있고, 이 직선 좌표위에 우체국을 하나 놓을건데 마을 사람들의 수와 각 마을 위치를 고려해 가장 좋은 위치를 선정하는 문제이다.
마을위치 값이 -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;
    }
}