[프로그래머스/Python] 이분탐색 - 입국심사

Sujin Lee·2022년 5월 19일
0

코딩테스트

목록 보기
44/172
post-thumbnail

접근 방법

  • 임의의 시간 동안 몇 명이 심사 받을 수 있는지 확인하고 이 값을 최소로 만들기
  • 시간의 최소, 최대 범위를 구하고 중간 값이 n명을 심사 할 수 있는 시간인지 확인하며 이분 탐색을 진행
    중간 값 시간 동안 ,
  • n명보다 많이 심사 가능 -> 중간값 기준 왼쪽 범위 탐색
  • n명보다 적게 심사 가능 -> 중간값 기준 오른쪽 범위 탐색
  • 임의의 시간동안 몇 명을 심사 할 수 있는지 확인하는 방법

풀이

def solution(n, times):
    answer = 0
    left = min(times)
    right = max(times) * n
    while left <= right:
        mid = (left + right) // 2
        check = 0
        for time in times:
        	# check는 모든 심사관들이 mid분 동안 심사한 사람의 수
            check += mid // time
            # mid분 동안 심사한 사람의 수가 n명 이상의 심사를 할 수 있다면 break
            if check >= n:
                break
        # 심사한 사람의 수가 심사 받아야할 사람의 수보다 많거나 같은 경우
        if check >= n:
            answer = mid
            right = mid -1
        # 심사한 사람의 수가 심사 받아야할 사람의 수보다 적은 경우
        elif check < n:
            left = mid + 1
    return answer
  • right = 가장 비효율적으로 심사했을 때 걸리는 시간 = 가장 긴 심사시간이 소요되는 심사관에게 n명 모두 심사받는 경우
  • left <= right 경우
    • mid = (7 + 60) // 2 = 33
    • for time in times:
      • check = 0 + 33 // 7 = 4, 4는 6보다 크거나 같나? No
      • check = 4 + 33 // 10 = 7, 7은 6보다 크거나 같나? Yes -> break
    • 심사한 사람의 수 check 가 심사 받아야할 사람의 수 6보다 많거나 같음
      • answer = mid = 33
      • right = 32

    • mid = (7 + 32) // 2 = 19
    • for time in times:
      • check = 0 + 19 // 7 = 2, 2는 6보다 크거나 같나? No
      • check = 2 + 19 // 10 = 3, 3은 6보다 크거나 같나? No
    • 심사한 사람의 수 check 가 심사 받아야할 사람의 수 6보다 적음
      • left = mid + 1 = 20

    • mid = (20 + 32) // 2 = 26
    • for time in times:
      • check = 0 + 26 // 7 = 3, 3는 6보다 크거나 같나? No
      • check = 3 + 26 // 10 = 5, 5은 6보다 크거나 같나? No
    • 심사한 사람의 수 check 가 심사 받아야할 사람의 수 6보다 적음
      • left = mid + 1 = 27

    • mid = (27 + 32) // 2 = 29
    • for time in times:
      • check = 0 + 29 // 7 = 4, 4는 6보다 크거나 같나? No
      • check = 4 + 29 // 10 = 6, 6은 6보다 크거나 같나? Yes
    • 심사한 사람의 수 check 가 심사 받아야할 사람의 수 6보다 많거나 같음
      • answer = mid = 29
      • right = 28

    • mid = (27 + 28) // 2 = 27
    • for time in times:
      • check = 0 + 27 // 7 = 3, 3은 6보다 크거나 같나? No
      • check = 3 + 27 // 10 = 5, 5은 6보다 크거나 같나? No
    • 심사한 사람의 수 check 가 심사 받아야할 사람의 수 6보다 적음
      • left = mid + 1 = 28

    • mid = (28 + 28) // 2 = 28
    • for time in times:
      • check = 0 + 28 // 7 = 4, 4는 6보다 크거나 같나? No
      • check = 4 + 28 // 10 = 6, 6은 6보다 크거나 같나? Yes
    • 심사한 사람의 수 check 가 심사 받아야할 사람의 수 6보다 많거나 같음
      • answer = mid = 28
      • right = 27

  • left > right로 반복문 탈출!
profile
공부한 내용을 기록하는 공간입니다. 📝

0개의 댓글