[프로그래머스] Lv.3 입국 심사 - 파이썬(Python) 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

 

문제

 

 

💡 문제 풀이

---

이분 탐색

이분 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

 

접근 방법

• 찾고자 하는 시간을 범위로 하여 이분 탐색 
• 임의의 시간 동안 몇 명을 심사할 수 있는지 확인
• left : min(times)  -> n이 1일 경우를 고려
• right : n*min(times) 

 

 

💻 문제 코드

---

def solution(n, times):
    left, right = min(times), min(times)*n
    
    while left <= right:
        mid = (left + right) // 2
        check = 0
        
        #check 은 모든 심사관들이 mid분 동안 심사한 사람의 수
        for x in times:
            check += mid//x
            # 중간에 mid분 동안 n명 이상의 심사를 할 수 있다면 반복문 탈출
            if check >=n:
                break
        
        # 심사한 사람의 수가 심사 받아야 할 사람의 수보다 많거나 같은 경우
        if check >=n:
            answer = mid
            right = mid -1
        # 심사한 사람의 수가 심사 받아야 할 사람의 수보다 적은 경우
        elif check <n:
            left = mid +1
            
    return answer

 

📖 중요 포인트

---

• 찾고자 하는 시간을 범위로 하여 이분 탐색 

이분탐색 문제는 '이분 탐색의 범위는 무엇으로 할지'와 '이분 탐색의 기준을 무엇으로 할지'를 잡는 부분이 어려운 거 같다. 딱 이 부분이 핵심인 거 같고 문제를 많이 풀어보면서 감을 잡아야 할 거 같다

 

 

 

 

 

 

[참고 자료]

- 그림: https://happy-obok.tistory.com/10