[프로그래머스] 입국심사, 파이썬

💡 문제 해결 아이디어

🛠 피드백

• 다른 사람의 풀이를 보고 해결한 문제이다!
• 문제를 다르게 해석하자면, 모든 사람들이 심사를 받는데 부족하지도, 넘치지도 않는 최적의 값을 찾는 문제이다
• 설정한 시간 동안 n명 초과의 사람을 심사했다면 너무 시간이 많은 것이고, n명 미만의 사람을 심사했다면, 너무 시간이 부족한 것이다.
• 딱 n명 심사했더라도, 몇 분 시간이 남았을 수도 있으니 시간이 많을 "수도" 있다라는 것을 생각하자.

💻 작성된 코드(수정)

def solution(n, times):
	# 가능한 최솟값과 최댓값을 left와 right로 설정
    left = 1
    right = max(times) * n
    
    # 이분탐색이니 left가 right 이하인 동안
    while left <= right:
    	# 가운데 : 더하고 2로 나눈 몫(정수)
        mid = (left+right)//2
        # 심사한 사람 수
        people = 0
     	
        for time in times:
        	# 해당 심사대에서 주어진 시간동안 심사 받은 수 더하기
            people += mid//time
            
            # 중간에라도 이미 n명보다 많이 심사했다면 break
            if people >= n:
                break
        # n명 초과 심사했다면, 시간이 너무 많은 것
        # 딱 n명 심사했더라도, 시간이 남을 가능성 있음
        if people >= n:
            answer = mid
            right = mid -1
        # n명 미만 심사했다면, 시간이 너무 부족하다
        else :
            left = mid + 1
    return answer

• 총 2가지를 얻어갈 수 있었던 문제

1. input의 최대길이가 지나치게 길고, 특정 값을 찾아야 하는 문제라면 이분탐색을 의심해보자
2. 이분탐색의 전반적인 구조를 외우도록 하자 (left, right, while, for, break, if...)