[programmers-python] 이분탐색

참고 : https://m.post.naver.com/viewer/postView.nhn?volumeNo=27217004&memberNo=33264526

이진 탐색 문제 기본유형만 풀어봤어서 이렇게 어려운줄 몰랐다..
문제를 읽었을 때 왜 이진탐색인지 판단도 안서서 고민을 정말 많이 했다.
결국 다른 블로그들을 참고 했는데 이분탐색 문제에서는 다음과 같은 기준을 먼저 설정해놓는 게 중요한 듯하다.

• 무엇을 이분탐색 값으로 설정할 것인가
• 이분탐색의 left, right 값을 변화시킬 기준은 무엇인가

입국심사

Try

def solution(n, times):
    maxTime = max(times) * n
    minTime = 1

    return binary_search(n, times, minTime, maxTime)

def binary_search(n, times, minTime, maxTime):
    mid = (minTime + maxTime) // 2

    people = 0
    for t in times:
        people += mid // t
        if people >= n:
            break

    if people == n:
        return mid

    if people > n :
        return binary_search(n, times, minTime, mid-1)
    elif people < n:
        return binary_search(n, times, mid+1, maxTime)

Answer

def solution(n, times):
    answer = 0

    left = 1
    right = n * max(times) # 최대 범위

    while left <= right:
        mid = (left + right) // 2

        count = 0
        for time in times:
            count += mid // time
            # 심사 인원수를 넘으면 다음 단계
            if count >= n: break

        # n명을 심사 할 수 있는 경우
        # 한 심사관에게 주어진 시간을 줄여본다.
        if count >= n:
            answer = mid
            right = mid - 1
        # 없는 경우
        elif count < n:
            left = mid + 1

    return answer

• https://wwlee94.github.io/category/algorithm/binary-search/immigration/

징검다리

#coding:utf8
def solution(distance, rocks, n):
    answer = 0
    left = 1
    right = distance
    rocks.sort()
    while left <= right:
        mid = (left + right) // 2
        pre_rock = 0
        num_of_rock = 0
        m_min = 1000000001
        for rock in rocks:
            if rock - pre_rock < mid:
                num_of_rock += 1
            else:
                m_min = min(m_min, rock-pre_rock)
                pre_rock = rock
                
        if num_of_rock > n:
            right = mid - 1
        else:
            answer = m_min
            left = mid + 1
    
    return answer

• https://coreenee.github.io/2020/05/13/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4(%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC)/