18310 - 백준 - 안테나

1. 문제 출처

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

18310번: 안테나

2. 풀이

그냥 구현을 해보자

# 시간 초과 
N = int(input())
home_list = list(map(int,input().split()))

def solution():
# 최소길이 구하기
    min_dis = total_distance(home_list[0])
    antenna = home_list[0]
    for idx in range(1,N):
        if min_dis  >  total_distance(home_list[idx]):
            min_dis = total_distance(home_list[idx])
            antenna = home_list[idx]
            continue
        if min_dis == total_distance(home_list[idx]):
            antenna = min(antenna ,home_list[idx] )
          # 최소 길이가 되는 안테나 위치 반환
    print(antenna)

# 안테나 위치에 따른 총 거리 구하기
def total_distance(antenna):
    total = 0
    for home in home_list:
        total +=(abs(home-antenna))
    return total

        
        
solution()

삐빗 틀렸습니다.

이유는 문제를 잘보면 N의 범위가  (1≤N≤200,000)인데 시간제한은 1초이다 위에 구현한 코드는 O(N)이므로  1초가 넘을 수 있다...

다시한번 문제를 잘 살펴보면 규칙이 발견되는 것을 알 수 있다 그것을 Median에서 모든 거리가 최소가 된다는 것이다.  

그럼 내장된 함수 sort를 사용하면(기본적으로 퀵정렬을 사용한다) O(NlogN) 이므로 시간내에 해결할 수 있다.

N = int(input())
home_list = list(map(int,input().split()))

def solution():
    home_list.sort()
    print(home_list[int(N/2) - (N+1)%2])
      
solution()