[백준] 18310 안테나 JAVA

 

그리디 알고리즘 문제

 

접근방식

- 전봇대의 왼쪽, 오른쪽 집의 갯수가 같아야 한다 = > 1 3 5 7 이라 가정했을 때 전봇대가 3->2로 이동한다고 치면, 오른쪽에 집이 3개가 있기 때문에 거리의 합이 +3-1이되어 +2가된다. 3~5에서 이동은 좌측, 우측 집이 2개씩이기때문에 총 길이의 합의 변화가 없다.

 

3~5에서의 이동만 총 길이가 늘어나지 않기 때문에 최소치이다.

 

집의 갯수가 홀수일 경우, 집들의 중간값에있는 위치만이 좌측 우측의 집의 갯수가 동일하므로 유일한 답

집의 갯수가 짝수일 경우 중간값 2개중 작은것이 답(문제의 조건때문에)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        int idx = (N-1) / 2;
        System.out.println(arr[idx]);
    }
}