[백준 18310 파이썬] 안테나

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

실패한 코드

import sys
input = sys.stdin.readline

n = int(input().rstrip())
house = list(map(int, input().rstrip().split()))

house.sort()

distance_sum = 1e9
distance = -1

for i in range(len(house)):
    temp = 0
    for j in range(len(house)):
        temp += abs(house[i] - house[j])
    
    if temp != distance_sum:
        if distance_sum > temp:
            distance_sum = temp
            distance = house[i]
            
    elif temp == distance_sum:
        if distance > house[i]:
            distance = house[i]

print(distance)

시간 복잡도가 n^2인데 n의 범위가 200,000이라서 시간초과가 발생했다.

정답 코드

import sys

input = sys.stdin.readline

N = int(input())
house = list(map(int, input().rstrip().split()))

house.sort()
print(house[(N - 1) // 2])

수학적으로 생각하면 간단하게 풀 수 있는 문제이다.

모든 집까지의 거리의 총합이 가장 작으려면 일직선 상에서 가운데에 가까울 수록 총합이 적어진다.

그래서 배열에 집의 위치를 저장하고 정렬 후 중앙값을 찾아서 출력하면 된다.

홀수인 경우는 n / 2해서 중앙값을 찾으면 된다.
그러나 짝수인 경우에는 중간값이 2개가 나오는데 그 중 왼쪽에 위치한 집을 찾는다.
-> (n - 1)을 하고 2로 나눈 몫을 가져오면 해결된다.