99클럽 코테 스터디 3일차 TIL - 프로그래머스 입국심사(43238) Swift & Python

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
프로그래머스	43238	입국심사	이분탐색	Lv.3	Swift, Python

🚀 나의 접근 방법

입력 조건을 보면 1,000,000,000 이상으로 매우 크기 때문에 이분 탐색으로 접근했다.

구해야 하는 값은 모든 사람이 심사를 받는데 걸리는 시간의 최솟값이다. 그러면 최악의 경우는 모든 사람이 가장 오래 걸리는 심사관에게 심사 받는 것이다. 즉, 이진 탐색의 범위는 0 ~ (times에서 가장 큰 값 * n)이다.

범위를 정했으니 이진 탐색을 통해 선택한 중간값(모든 사람이 심사를 받는데 걸리는 시간) 안에 심사관들이 처리할 수 있는 사람 수를 구해야 한다.

count = 0 # 이진 탐색 중에 선택한 임의의 '모든 사람이 심사를 받는데 걸리는 시간' 안에 심사관들이 처리할 수 있는 사람 수
for time in times:
	count += 중간값(모든 사람이 심사를 받는데 걸리는 시간) // time(각 심사관의 심사하는데 걸리는 시간)

위와 같이 총 시간을 수행하는 데 걸리는 시간으로 나눈 몫으로 시간 안에 처리할 수 있는 사람 수를 구할 수 있다.

✍️ 나의 코드

Swift

import Foundation

func solution(_ n:Int, _ times:[Int]) -> Int64 {
    var start = 0
    var end  = times.max()! * n
    
    while start <= end {
        let mid =  (start + end) / 2
        
        var count = 0
        for time in times {
            count += mid / time
        }
        
        if count >= n {
            end = mid - 1
        } else {
            start = mid + 1
        }
    }
    return Int64(start)
}

Python

def solution(n, times):
    start = 0
    end = max(times) * n
    
    while start <= end:
        mid = (start + end) // 2
        
        count = 0
        for time in times:
            count += mid // time
        
        if count >= n:
            end = mid - 1
        else:
            start = mid + 1
            
    return start

🤔 회고 및 개선사항

이분 탐색으로 접근하겠다고 정했으면 어떤 데이터를 이분 탐색할 건지 정하는 게 중요하다. 이번에 탐색 데이터를 빠르게 판단하지 못해서 아쉽다.

일반적인 이분 탐색 문제라면 문제에서 반환 또는 출력해야 하는 값에서 힌트를 얻을 수 있을 것 같다. 또한 제한사항이나 조건을 잘 살펴보면 도움이 될 것이다.