이것이 취업을 위한 코딩테스트다 15장. 이진탐색 문제

29 공유기 설치

• 1회: 오답 - 문제에 대한 감도 못 잡음, 문제를 이해하고 나니 떡볶이 떡 문제랑 비슷하단 걸 알았다

모범답안: github.com/ndb796/python-for-coding-test/blob/master/15/3.py

ndb796/python-for-coding-test

해설

• 집의 좌표와 공유기의 갯수(C)를 입력 받기
• 집의 좌표를 정렬하기
• 집끼리의 최대 거리를 구하기 위한 이진탐색 수행
  • 맨 처음에 mid는 중간점: (첫번째 집 좌표 + 마지막 집 좌표) // 2
  • 항상 첫번째 집부터 공유기를 설치한다고 할 때, 공유기 사이의 간격이 mid를 만족하는 집의 갯수를 찾는다. (마지막 집까지 찾기)
  • 설치한 공유기의 갯수가 C보다 크거나 같으면,
    • answer = mid로 저장
    • mid 값을 늘이고: start 포인트의 지점을 뒤로 이동. start = mid + 1 
  • 설치한 공유기의 갯수가 C보다 작으면,
    • mid 값을 줄이고: end 포인트의 지점을 앞으로 이동. end = mid - 1
• 이진탐색을 완료하면 answer 반환

 

n = 5
c = 3
array = [1, 2, 4, 8, 9]

start = 1
end = array[-1] - array[0]

answer = -1

while start <= end:
    mid = (start + end) // 2
    
    value = array[0]
    count = 1
    
    for i in range(1, n):
        if array[i] >= value + mid:
            count += 1
            value = array[i]
    
    if count >= c:
        answer = mid
        start = mid + 1
    else:
        end = mid - 1

return answer