[프로그래머스_이분탐색_Lv3] 입국심사

입국심사

문제 링크

나의 풀이

🙅‍♂️ 1차 풀이

def solution(n, times):
    answer = 0
    left = 1
    right = max(times) * n

    while left <= right:
        mid = (left + right) // 2
        customer = 0
        for i in times:
            customer += mid // i

        if customer > n:
            right = mid -1
        elif customer <= n:
            answer = mid
            left = mid + 1

    return answer

print(solution(6, [7, 10])) # 결과값으로 28이 나와야하지만 29가 나옴

• 문제 풀이를 위한 접근 방식이나 전체적인 로직의 플로우는 맞았으나 오답이 나왔다. 내가 원했던 값보다 1이 크게 나왔다.
• 하단의 if문 조건과 answer = mid 이 코드의 위치가 잘못된 것으로 생각 되었다. 이 부분을 이해하는데 시간이 오래 걸렸다.
  while 문 조건의 범위, if문의 범위의 관계를 아주 잘 생각하고 따져야한다.

🙆‍♂️ 2차 풀이

def solution(n, times):
    answer = 0
    left = 1
    right = max(times) * n

    while left <= right:
        mid = (left + right) // 2
        customer = 0
        for i in times:
            customer += mid // i

        if customer >= n:
            answer = mid
            right = mid -1
        elif customer < n:
            left = mid + 1

    return answer

• 이진 탐색으로 풀 수 있는 문제다. 이 방법으로 풀때는 값의 범위와 mid 값을 무엇으로 설정하느냐가 관건인데 무엇으로 정할지 생각해내는 것이 어려웠다. 이것이 핵심인 것 같고 핵심만 잘 설정하면 코드를 써 내려가는 것은 크게 어렵지 않았다.

• 이 문제의 경우 right값은 times 배열에서 가장 큰 값(가장 오래걸리는 시간)으로만 계산했을 때의 값을 right값으로 설정하였다. 그리고 기준(customer)은 mid값으로 계산하였을때 처리 할 수 있는 인원이다.

• 위의 오답코드와 차이점이 있다면, customer==n 일때 최소값이 있는 왼쪽 구간을 선택한다는 것이다.