[프로그래머스] 입국심사

입국심사 | Lv.3
https://school.programmers.co.kr/learn/courses/30/lessons/43238

 

 

 

 

 

작성 코드 (시간 초과)

 

def solution(n, times):
    answer = 0 
    wait = times[:]
    for person in range(n):
    	# 가장 짧게 끝나는 곳의 인덱스 반환
        min_wait = wait.index(min(wait))
        # 해당 번호에 줄을 선다 -> 이후 다른 사람은 시간이 더 걸린다 -> 더해준다!
        wait[min_wait] += times[min_wait]
        
    # 입국 심사가 진행되는 시간까지 포함이라 맨 마지막에는 진행 시간을 빼줘야 함
    return wait[min_wait] - times[min_wait]

 

• 최소 값이라 힙을 쓰고 싶었는데 그럼 인덱스를 활용 못하니까, 즉 몇 번째 심사대인지 대기시간을 파악하지 못하니까 사용하지 못함
• 이분 탐색 문제인데 어떻게 연관 짓나 감이 안 잡힘

 

 

이상 코드

 

def solution(n, times):
    left, right = min(times), max(times) * n
    
    while left <= right:
        mid = (left + right) // 2
        
        # mid 시간 동안 검사할 수 있는 사람의 수
        total_person = 0
        
        # 검사대를 돌면서 해당 시간 동안 몇 명을 검사할 수 있는지 더함
        for time in times:
            total_person += mid // time
        
        # 만약 총 검사할 수 있는 사람이 n보다 크거나 같다면 mid 값을 줄일 수 있음
        if total_person >= n:
            right = mid - 1
        elif total_person < n:
            left = mid + 1
        
    return left

 

• 총 걸린 시간을 이분탐색함
• https://happy-obok.tistory.com/10 블로그 내에 있는 풀이 설명 그림 참고 ! 아주 잘 정리하심