백준 - 우체국

문제 설명

각 마을들이 위치한 수직선 상에서 마을에 거주하는 각 사람들까지의 거리의 합이 최소가 되는 곳에 우체국을 건설하려고 할 때, 우체국을 세울 위치를 구하는 문제이다.

각 사람들까지의 거리의 합이 최소가 되는 곳에 우체국을 건설해야 하니 과반수가 넘는 인원에 대해서 최대한 가깝게 우체국을 건설하는 것이 좋다고 판단하였다.

우선 거리기반(오름차순), 인구수 기반(내림차순)으로 정렬한다.

하나씩 순회하면서 거쳐간 인원 인구수를 파악한 후 과반수 이상의 사람이 살고 있는 경우라면 해당 위치에 우체국을 건설한다.

단 원소의 값이 최소 + - 10억이므로 거쳐간 인구수에서 int 자료형은 이슈가 될 수 있으니 주의해야한다.

풀이

public static void main (String[] args) throws java.lang.Exception {
	    Reader reader=new Reader();
	    int n=reader.n;
	    long x[][]=reader.arr;
	    // 우체국 위치를 정하는 문제이다.
	    // 각 사람들까지의 거리의 합이 최소가 되는 위치
	    // 사람이 많은 마을에게 가까워야 한다.
	    long total = Arrays.stream(x).map(a -> a[1]).reduce(0L,Long::sum);
	    Arrays.sort(x,(a,b)->{
	        if(a[0] == b[0] ){
	            return (int) (b[0]- a[0]);
	        }
	        
	        return (int) (a[0] -b[0]); 
	    });
	    
	    // 범위가 커서 결정을 해야되는데.. 어떻게 하지?
	    long sum=0;
	    for(long[] vals: x){
	        sum+=vals[1];
	        
	        if(sum >= (total+1)/2){ // 
	            print(String.valueOf(vals[0]));
	            break;
	        }
	    }
	    
	}
	
	static void print(String s){
	    System.out.println(s);
	}
	
	static class Reader{
	    static Scanner sc=new Scanner(System.in);
	    static StringTokenizer st;
	    int n;
	    long [][]arr;
	    
	    public Reader(){
	        n=toInt(sc.nextLine());
	        arr=new long[n][2];
	        
	        for(int i=0; i<n; i++){
	            createToken();
	            arr[i][0]=toLong(st.nextToken());
	            arr[i][1]=toLong(st.nextToken());
	        }
	    }
	    
	    private static int toInt(String s){
	        return Integer.parseInt(s);
	    }
	    
	    private static long toLong(String s){
	        return Long.parseLong(s);
	    }
	    
	    private static void createToken(){
	        st=new StringTokenizer(sc.nextLine());
	    }
	    
	}