1. 문제정보
https://www.acmicpc.net/problem/18310
18310번: 안테나
첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다.
www.acmicpc.net
2. 해결전략
처음에는 얼핏 집들의 위치 값 중 평균 즈음에 안테나를 설치하면 해결이 가능할 것 같았다. 하지만 소수점의 위치가 나오는 경우도 있고 이러한 의도로 만들어진 문제가 아닐 것이라고 생각했다. 안테나가 가장 좌측에 있을 때의 거리를 구하고, 안테나의 위치를 이동하면서 계산하는 게 가장 단순한 풀이 방식일 것이다.
하지만 이중 포문으로 풀이하는 경우 최대 20만 x 20만의 연산이 발생하기 때문에 시간 초과가 나올 것이 분명했다. 절대 값의 성질을 고민해보니 안테나의 좌측, 우측에 있는 집의 수만 알 수 있다면 손 쉽게 계산할 수 있다는 걸 알았다.
3. 코드
n = int(input())
input_data = list(map(int, input().split()))
cnt_array = [0] * 100001
for i in input_data:
cnt_array[i] += 1
current = 1 # 현재 안테나위치
left = 0 # 안테나 좌측에 있는 집의 수
right = n-left # 안테나 우측에 있는 집의 수
distance = sum(input_data) - n
while current <= 100001:
current += 1 # 안테나 위치이동
left += cnt_array[current-1] # 안테나 위치가 이동하면 좌측의
right = n-left
# 이전 안테나 위치가 최고효율인 경우
if distance <= distance + left - right:
current -= 1
break
else:
distance = distance + left - right
print(current)