📙[Algo] 23.12.28 알고리즘

18310번: 안테나

문제 요약
안테나 설치 ⇒ 모든 집까지의 거리의 총 합이 최소가 되도록
집이 위치한 곳에서만 설치 가능

시간 제한
시간 제한 1초 (1억개 연산)

입력
집의 수 N (1~200,000)N개의 집의 위치가 주어짐(1~100,000)

출력
안테나를 설치할 위치 값 출력

 

접근법

1. 완전 탐색으로 접근한다면?

• 모든 집에 안테나 하나씩 설치하며 거리를 비교해본다고 가정했을 때
• 집의 수 N이 최대 200,000개가 가능하고, 안테나를 세울 때마다 거리 비교를 해야하기 때문에 연산 횟수가 총 200,000*200,000개, 즉, 400억의 연산이 필요하므로 시간 초과가 발생한다.
• 어떻게 하면 연산 횟수를 최소화 할 수 있을 지 생각해보자! => 테스트 케이스를 통해 직접 규칙성을 찾아보자.

2. 규칙성 찾기

1 5 7 9 가 입력으로 주어진다면 ..

*

0 4 6 8 = 18 : x +1 (불만 5 7 9)

   *

4 0 2 4 = 10 : x (불만 1 7 9)

      *

6 2 0 2 = 10 : x (불만 1 5 9)

         *

8 4 2 0 = 14 : x (불만 1 5 7)

⇒ 중앙값이 답이 된다.

 

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public 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[] homes = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            homes[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(homes);

        int idx = N%2==0? N/2-1 : N/2;
        System.out.println(homes[idx]);
    }
}