[백준_2110] 중, 이분 탐색, 공유기 설치

생각 포인트

가장 인접한 두 공유기 사이의 최대 거리를 구해야 하므로 N개의 집의 양 끝에는 공유기가 무조건 설치된다.

그 다음 공유기 설치 위치는 좌표적으로 1번째와 N번째 공유기 중간에 가장 가까운 곳에 위치해야 한다. (순서상 중간이 아니다)

이 부분이 이진 탐색과 연결이 된다.

그럼 중간 좌표와 가장 주변 집의 좌표들 차이의 최솟값을 구해 최소가 되는 지점의 index에 공유기를 설치한다.

그 다음 공유기는 방금 설치한 공유기를 기준으로 1번째와 N번째 공유기 위치와의 거리 중 긴 곳 영역에 설치된다. 이후 반복.

이란 생각으로 풀었는데, 완전 오답 풀이였다.... 일단 이 방식은 딱 중간 가까운 공유기를 설치하기 때문에 공유기 개수가 짝수일 경우에는 오답이다..

 

정답 코드를 작성하기 위한 핵심은 이분 탐색을 할 '주체'를 잘 선정하는 것이다. 아는 좌표적으로 이분 탐색을 진행하였는데, 문제를 풀기 위해서는 공유기기 설치 최소거리를 이분 탐색 해야한다.

 

내 코드 - 오답

import sys

house = 0
t = []
N, C = sys.stdin.readline().split()
house = [int(sys.stdin.readline().strip()) for _ in range(int(N))]
house.sort()


def wifi(arr, left, right, C):
    global t
    ileft = left # 가장 왼쪽집의 인덱스
    iright = right # 가장 오른쪽 집의 인덱스
    di = 0 # 중간값과 집과의 거리 차이
    j = 0 # 중간갑과 집과의 거리 차이가 최소인 곳의 인덱스 값
    center = (arr[ileft] + arr[iright]) // 2 # 거리상 중간값
    if 2+len(t) < C :
        for i in range(len(arr)): # 거리상 중간값과 집의 위치가 최소가 되는 i를 찾음
            if abs(center-arr[i]) <= abs(center-arr[i-1]): # i번 째 집과 중간값 거리차가 i-1번쨰 집과 중간값 거리차이보다 작은 경우
                j = i # 이 때의 인덱스를 j로 저장
        if arr[j] - arr[ileft] <= arr[iright] - arr[j]: # 중간값 기준으로 왼쪽 집과의 거리가 더 짧을 경우
            t.append(arr[j]-arr[ileft])
            ileft = j # 탐색 영역의 가장 왼쪽값이 j즉 중간값으로 바뀜, 오른쪽 영역에서 이분 탐색 진행
            wifi(arr, ileft, iright, C)

        else:
            iright = j
            t.append(arr[iright]-arr[j])
            wifi(arr, ileft, iright, C)

wifi(house, 0, len(house)-1, int(C))
print(max(t))

 

정답 코드

import sys

N, C = map(int, input().split())
house = [int(sys.stdin.readline()) for _ in range(N)]

house.sort()

#와이파이 간의 간격을 이분탐색으로 구해야함.
left = 1
right = house[-1] - house[0]
answer = 0
while right >= left:
    mid = (left + right) //2
    wifi_cnt = 1 # 처음에 하나 설치했다고 가정
    before_install = house[0] # 처음 설치 위치
    for i in range(len(house)):
        if house[i] >= mid + before_install: # 각각의 집들이 와이파이 설치된 이전 집으로부터 mid 간격 보다 클 경우
            wifi_cnt += 1 # 설치
            before_install = house[i]

    if wifi_cnt < C: # 설치해야할 와이파이 개수보다 적게 설치 되었으면 설치 간격을 줄인다.
        right = mid - 1
    else: # 설치해야할 와이파이 개수보다 많이 설치 되었으면 설치 간격을 늘린다.
        left = mid +1
        ans = mid # while 종료를 대비하여 ans에 저장

print(ans)