[항해99] 99클럽 코테 스터디 3일차 TIL + 이분탐색(프로그래머스 입국심사)

오늘의 학습 키워드

• 이분탐색
• 프로그래머스 입국심사

공부한 내용

1. 문제 이해

• n명의 사람이 입국심사를 받아야 함
• 각 심사관마다 심사하는데 걸리는 시간이 다름
• 모든 사람이 심사를 받는데 걸리는 최소 시간을 구해야 함

2. 접근 방법

• 이분탐색을 통해 최적의 시간을 찾아가는 방식 사용
• 탐색 범위
  • 최소 시간(left): 1
  • 최대 시간(right): 가장 긴 심사시간 × 인원수

3. 핵심 로직 설명

• 중간값(mid) 시간 동안 처리할 수 있는 총 인원 계산
• 각 심사관별로 주어진 시간 동안 처리 가능한 인원을 합산
• 처리 가능 인원이 목표 인원보다 많으면 시간을 줄임
• 처리 가능 인원이 목표 인원보다 적으면 시간을 늘림

# 항해 99 Day 3
# 프로그래머스 입국심사
# 이분탐색을 통해서 총 걸리는 시간을 점점 좁혀나가는 형식으로 푸는 문제

def solution(n, times):
    answer = 0
    # right는 가장 오래 걸리는 심사관이 모든 사람을 심사하는 경우로 나올 수 있는 최대 시간
    left, right = 1, max(times) * n 

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

        # 심사자가 n명이기 때문에 각 심사관이 mid 시간동안 심사할 수 있는 사람 수를 구해서 더함
        for i in times:
            people += mid // i
            # 만약 mid 시간동안 심사한 사람이 n명보다 크다면 break
            if people > n:
                break
        # 만약 mid 시간동안 심사한 사람이 n명보다 크거나 같다면 answer에 mid를 저장하고 right를 mid - 1로 변경
        if people >= n:
            answer = mid 
            right = mid - 1
        else:
            left = mid + 1

    return answer

오늘의 회고

이분 탐색 문제라는 것은 문제를 보고 떠올릴 수 있었다. 그러나, 이분 탐색 알고리즘이 완전히 숙지되지 않았는지 구현하는데 어려움이 있었다. 총 걸리는 시간을 좁혀나가는 형태로 접근해야 하는데 떠오르지 않았다. 풀이를 보고 심사자가 n명이기 때문에 for문을 활용해서 총 심사 시간을 계산하는 것을 알 수 있었다. 유연하게 풀이를 할 수 있도록 많이 풀어봐야 할 것 같다.