[Python] 백준 18310번 - 안테나

1. 문제정보

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

18310번: 안테나

 

 

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)