안테나

풀이

 처음에는 번호가 가장 작은 지점부터 가장 큰 지점까지 1씩 증가시키면서 그 지점까지의 거리의 합을 비교하는 완전탐색으로 접근했었다. 하지만 시간초과 판정이 났다.

• 잘못된 풀이

n = int(input())
data = list(map(int, input().split()))
data.sort()
min = 100000
result = -1

for i in range(data[0], data[-1]+1):
    sum = 0
    for j in data:
        sum += abs(i-j)
    if sum < min:
        min = sum
        result = i

print(result)

 그래서 어떻게 하면 효율적으로 정답을 구할 수 있을까 생각하다가 평균이 떠올랐다. 평균을 구하는데 만약 소수면 그 언저리가 정답이겠거니 하고 생각했었다. 그래도 코드를 치기에 앞서서 반례가 있을까 생각했는데 역시 존재했다. 만약 위치가 1 4 8 11일 경우 평균을 적용하면 정답은 6이 되지만 실제로는 4,5,6,7,8이 최소값이었고 정답은 4였다. 따라서 평균이라는 개념은 이 문제에 적용하면 안된다고 결론을 내렸다. 대신 중간값이 떠올랐고 몇번의 시도에 걸쳐서 반례를 찾으려 시도했지만 찾을 수 없었고 이 문제의 핵심은 중간값을 찾는거라고 결론을 내렸다.

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

data.sort()

# 홀수
if len(data) % 2 != 0:
    print(data[len(data) // 2])

# 짝수
else:
    print(data[len(data) // 2 -1])

시간복잡도 : O(n+m) (N,M에 대해)