코딩테스트/파이썬

[프로그래머스/파이썬] 입국심사 풀이 (이진탐색, 이분탐색, python)

JI NY 2025. 5. 16. 22:54

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

(이진탐색, 이분탐색, Python)

[프로그래머스/파이썬] 입국심사 풀이 (이진탐색, 이분탐색, Python)

 

 

1. 문제

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

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

 

 

2. 문제 해결 아이디어 (풀이)

 

1. 총 검사 시간(결과)을 이진탐색을 이용해서, 줄이고 늘려가면서 찾아가야 한다.

 

2. 각 심사관 당 심사 시간을 이용하여, 총 검사 시간을 기준으로 가능한 인원수를 모두 구한다.

- 총 가능한 인원수 += 총 검사 시간 // 심사관 한명 시간

 

3. 결과적으로 목표치(n) 보다 심사 가능 인원수가 더 많거나 같다면, 끝값(right)을 줄인다.

- 이때, 현재 비교했던 시간도 저장한다. (현재 시간대로 모든 사람을 심사할 수 있었기 때문이다)

 

4. 목표치(n)보다 심사 가능 인원수가 더 적다면, 시작값(left)을 늘린다.

이 방식을 반복해서 결과를 반환하면 된다.

 

3. 코드

def solution(n, times):
    answer = 0
    
    # 6명이 될때까지 디진탐색을 해야함
    # 이진탐색은 times를 순회하면서 심사관당 시간 내 가능한 인원을 구해야함. 
    
    # 이진탐색 기본 시간 구하기 
    left = min(times) # 1명 시간
    right = max(times) * n # 구할수 있는 최대의 시간 
    mid = 0 # 기준 시간 
    # 이진 탐색이 start >= end
    while left <= right: # 최소시간 <= 최대시간
        # 중앙값 시간 구하기.
        mid =  ( left + right ) // 2
        
        # 각 심사관 당 가능한 인원 구하기
        people = 0 # 현재 시간으로 심사 가능한 인원 수
        for time in times:
            people += mid // time # 현재 심사관이 시간 내 심사 가능한 인원 
        
        # 만약 기준보다 심사가능인원이 더 많다면?
        if n <= people:
            # 끝값 줄이기
            right = mid-1
            answer = mid # 현재 시간 저장
        # 만약 기준보다 심사가능 인원이 더 적다면?
        elif n > people:
            # 시작값 늘리기
            left = mid+1
            # 이 값은 mid가 될수 없음. 부족하므로
    
    return answer

 

 

4. 마무리

 

이 문제도 2번째로 푸는 거였는데, 이진 탐색 알고리즘을 이용한 풀이가 생각이 안 나서 결국 또 풀이를 찾아봤다.

다음에 다시 복습을 해야것다!

 

 

읽어주셔서 감사합니다~

도움이 되셨다면 공감 부탁드립니다 😊

 

- 참고자료