[파이썬(python)] 정렬 문제 안테나 백준 18310

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

18310번: 안테나

집의 개수와 위치 값이 주어질 때 안테나를 설치할 위치를 선택하는 프로그램 작성

예를들어 n = 4이고 위치가 1, 5, 7, 9일때

5의 위치에 설치해야 안테나로부터 모든 집까지의 거리의 총합이 4+0+2+4 = 10으로 최소가 된다

따라서 5를 출력하면 된다.

 

원래는 이렇게 생각했다.

안테나는 집이 위치한 곳에만 설치할 수 있으므로

모든 집의 좌표를 돌면서 거리 총합을 계산하고, 최소가 되는 값을 선택하기!

직접 모두 계산해보는 방법을 생각했다.

 

python 코드

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

#집의 좌표 오름차순 정렬
house.sort()

min_distance = 100000
for i in house:

#i가 안테나 위치
    distance = 0
    for j in house:
        distance += abs(i-j)
    if distance < min_distance:
        min_distance = distance
        min_antena = i

print(min_antena)

그런데 시간 초과가 났다. 쉬운 문제라고 생각했는데..

문제 풀면서 시간복잡도가 N*N이라 왠지 불안하긴 했는데 효율성을 높여야 하나보다.

 

 

다시 생각해보니 안테나는 집 위치들의 중간에 놓여야 가장 가까워진다는 것을 깨달았다.

다시말해 중간값이 되는 것이다. ㅜㅜ

이렇게 간단하다니.

 

최종 코드

 

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

print(house[(n-1)//2])

 

어쩐지 쉬운 문제인데 정답률이 30퍼 정도였는데,, 다들 비슷한 이유로 틀렸을 것 같다