[Python] 백준 #18310- 안테나

문제

---

 

18310번: 안테나

코드

---

My answer

import sys
input = sys.stdin.readline

n = int(input())
h = list(map(int, input().split()))
h.sort()
answer = dict()

for i in range(len(h)//2-1, len(h)//2+1):
    tmp = [abs(j-h[i]) for j in h]
    answer[h[i]] = sum(tmp)
answer = sorted(answer.items(), key=lambda x: (x[1], x[0]))

print(answer[0][0])

Another answer

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

# Median(가운데) 값을 출력합니다.
print(a[(n - 1) // 2])

풀이

---

맨처음에는 단순하게 브루트 포스로 해결하고자 하였다. 모든 집을 순회하며 안테나를 설치하고 길이들을 비교하였는데, 시간초과가 발생했다. 그래서 굳이 모두 비교할 필요없이 전체 집의 가운데만 비교해야겠다고 생각하였다.(가운데에 위치한 집들의 값이 당연히 최소가 될 것이기 때문에) 그래서 홀수일 때와 짝수일 때를 고려하여 홀수일때는 중간꺼, 짝수일 때는 중간, 중간+1에 안테나를 설치할 경우만 계산하여 비교하여 통과하였는데, 답은 훨씬 간단했다..

짝수일 경우 예를들어 6개의 집인경우, 3번째에 설치하든, 4번째에 설치하든 답은 동일했다. 문제에서 더 작은수를 출력하라고했기 때문에 another answer 처럼 단순하게 가운데에 있는 인덱스를 출력하면 되는 문제였다..