[백준] 18310. 안테나

18310. 안테나

18310번: 안테나

 

• 첫 풀이
  • 시간초과
  • (1≤N≤200,000) 이기 때문에 완탐을 해서 될 문제는 아님

from collections import deque
n=int(input())
lst=list(map(int,input().split()))
lst.sort()
home=deque()
for i in range(n):
    home.append(lst[i])
answer=1e9
idx=0

while home:
    q=home.popleft()
    result=0
    for l in lst:
        result+=abs(q-l)
    if answer>result:
        answer=result
        idx=q

print(idx)

 

• 두번째 풀이
• 개수가 홀수개여도 중간값 2개 다 거리계산하면 동일하기때문에 둘다 상관X
  • 아래 코드는 홀수일때 len(lst)//2 가 이미 중간값이기 때문에 오답

• 홀짝 상관없이 인덱스 중간값: 하나 빼고 /2
  • (len(lst)-1)//2 

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

#개수가 홀수개여도 중간값 2개 다 거리계산하면 동일하기때문에 둘다 상관X
#아래 코드는 홀수일때 len(lst)//2 가 이미 중간값이기 때문에 오답
print(lst[len(lst)//2-1])

 

• 다른 사람 풀이
  • 정렬한 후 중간값에서 거리 계산하는 것이 최소가 된다
  • 중간값이 아닌 위치가 되면 중간값에서 계산한 거리보다 계속 1씩 더 늘어나서 최소가 불가능

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

#개수가 홀수개여도 중간값 2개 다 거리계산하면 동일하기때문에 둘다 상관X
#아래 코드는 홀수일때 len(lst)//2 가 이미 중간값이기 때문에 오답
#print(lst[len(lst)//2-1])

#인덱스 맞추려면 1개빼고 //2
print(lst[(len(lst)-1)//2])