[백준 실버3] 18310번: 안테나 (그리디) - Java

18310번: 안테나

https://www.acmicpc.net/problem/18310

 

문제

일직선 상의 마을에 여러 채의 집이 위치해 있다. 이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 한다. 이 때 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다.
집들의 위치 값이 주어질 때, 안테나를 설치할 위치를 선택하는 프로그램을 작성하시오.
예를 들어 N=4이고, 각 위치가 1, 5, 7, 9일 때를 가정하자.

이 경우 5의 위치에 설치했을 때, 안테나로부터 모든 집까지의 거리의 총 합이 (4+0+2+4)=10으로, 최소가 된다.

입력
첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다.

출력
첫째 줄에 안테나를 설치할 위치의 값을 출력한다. 단, 안테나를 설치할 수 있는 위치 값으로 여러 개의 값이 도출될 경우 가장 작은 값을 출력한다.

예제 입력 1 
4
5 1 7 9

예제 출력 1 
5

---

풀이

시도

- 먼저 수직선상에 위치해있기 때문에 오름차순으로 정렬했다.

- int min = Long.MAX_VALUE, Math.abs()로 거리 계산? 당연히 시간 초과 날 것 같았고 실제로 해봐도 그러했다.

- 직관적으로 생각했을 때 안테나는 중간에 있어야 한다. 중간 어디냐는 것인데, '중간'이므로 n의 홀수/짝수를 고려해야 한다.

   "손해 보는 집 수 > 이득 보는 집 수" 일 때 안테나와 각 집 거리 합이 늘어난다.

  - 집이 홀수 채일 때: 가운데 번호 집에 있어야 한다.

     ex. 집 수가 5채일 때, (*인덱스대로 0~4번 집으로 칭함) 안테나가 2번 집보다 왼쪽으로 가면 2, 3, 4번 집이 손해를 본다(0, 1번 집은 2보다 앞에 있으면 이득, 2와 같은 위치에 있으면 손해). 반대로 2번 집보다 오른쪽으로 가면 0, 1, 2번 집이 손해를 본다. 따라서 2번 집에 있어야 한다.

  - 집이 짝수 채일 때: 가운데 선분의 시작 집에 있어야 한다.

     ex. 집 수가 4채일 때, (*인덱스대로 0~3번 집으로 칭함) 안테나가 1번 집과 2번 집 사이에 있다면 어디에 있든 거리가 같다. (선분 내에서 이동할 때 +1 수, -1 수 같아서 0)

     문제에서 안테나를 설치할 수 있는 위치 값으로 여러 개의 값이 도출될 경우 가장 작은 값을 출력한다고 했기 때문에 1번째 집에 설치해야 한다.

=> 인덱스가 (n-1)/2인 집의 위치가 안테나를 설치해야 하는 위치

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public void solution() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int[] houses = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());	
		for(int i=0; i<n; i++) {;
			houses[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(houses);
		System.out.println(houses[(n-1)/2]);
	}
	public static void main(String[] args) throws Exception {
		new Main().solution();
	}
}