문제

일직선 상의 마을에 여러 채의 집이 위치해 있다. 이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 한다. 이 때 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다.

집들의 위치 값이 주어질 때, 안테나를 설치할 위치를 선택하는 프로그램을 작성하시오.

예를 들어 N=4이고, 각 위치가 1, 5, 7, 9일 때를 가정하자.

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

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

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

문제만 보고 구현한 코드(시간초과)

문제만 보고 구현한 코드(시간초과) :

import java.util.*;

class House implements Comparable<House>{
	private int house;
	private int sum;
	public House(int house, int sum) {
		this.house = house;
		this.sum = sum;
	}
	public int getHouse() {
		return this.house;
	}
	public int getSum() {
		return this.sum;
	}
	public void addSum(int distance) {
		this.sum += Math.abs(this.sum - distance);
	}
	
	@Override
	public int compareTo(House other) {
		return Integer.compare(this.sum, other.sum);
	}
}
public class Main {

	public static void main(String[] args)throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		ArrayList<House>houses = new ArrayList<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < n ; i++) {
			houses.add(new House(Integer.parseInt(st.nextToken()), 0));
		}
		for(House now : houses) {
			for(int i = 0; i < n; i++) {
				now.addSum(houses.get(i).getHouse());
			}
		}
		Collections.sort(houses);
		System.out.println(houses.get(0).getHouse());
	}

}

코드해석 1

House 클래스를 생성 후 각각의 house 위치와 위치들의 차의 합을 구하기 위해서 메서드를 만들고
합을구하고 합들을 정렬 하기위해 인터페이스 Comparable<House> 를 상속받고 compareTo메서드를 오버라이딩해서 합을 기준으로 정렬한 후 처음 값을 출력해주는 코드를 작성하였다.

생각을 하지않고 문제를 풀고 구현하는데에만 집중한 거같다... 값들이 일직선상에있고 그 값들의 차가 가장 적은 것을 고르는 것은 간단하게 중간 값을 고르면 되는것인데... 문제푸는데에만 집중하지말자..

간단한 코드:

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            arrayList.add(sc.nextInt());
        }

        Collections.sort(arrayList);

        // 중간값(median)을 출력
        System.out.println(arrayList.get((n - 1) / 2));
    }
}