[프로그래머스] 고득점Kit (9) - 이분탐색 (파이썬)

1. 입국심사 (Lv. 3)

# 입국심사
def solution(n, times):
    answer = 0
    times.sort()
    left, right = 1, max(times)*n
    while left <= right:
        mid = (left+right)//2
        temp = 0
        for time in times:
            temp += mid // time
        if temp >= n:
            answer = mid
            right = mid - 1
        elif temp < n:
            left = mid + 1
    return answer

 

right = max(times)*n : 가장 긴시간으로 n명이 입국심사를 했을 때가 최댓값

이분탐색 실시

    - mid : 걸린 총 시간

    - temp : 해당 시간 안에 입국 심사를 할 수 있는 사람의 수

    - temp == n 을 목표로 이분탐색을 진행

---

2. 징검다리 (Lv. 4)

# 징검다리
def solution(distance, rocks, n):
    answer = 0
    rocks.sort()
    start, end = 1, distance
    while start <= end:
        mid = (start + end) // 2
        temp = 0
        other_rock = 0
        for rock in rocks:
            if rock - other_rock < mid:
                temp += 1
            else:
                other_rock = rock
        if temp > n:
            end = mid - 1
        elif temp <= n:
            answer = mid
            start = mid + 1
    return answer

 

바위 사이 거리의 최솟값중 가장 큰값을 구해야 하는 문제

right = distance : 도착지점이 최댓값

이분탐색 실시

    - mid : 바위사이 거리의 최솟값

    - temp : 제거해야 할 바위의 수

    - temp == n 을 목표로 이분탐색을 진행

 

이분탐색이 약점인데 결국 풀이를 보고야 말았다.

각 바위 사이의 거리를 구하기 위한 계산식의 풀이를 봤다.

현재 생각하고 있는 거리의 최솟값(mid) 보다 크다면 해당 바위를 other_rock에 할당해 줘야 했다.

일주일 후에 복습하기 위해 플래너에 기입해놨다.