ℹ️ 문제 정보
| 플랫폼 | 번호 | 제목 | 유형 | 난이도 | 언어 |
|---|---|---|---|---|---|
| 프로그래머스 | 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🤔 회고 및 개선사항
이분 탐색으로 접근하겠다고 정했으면 어떤 데이터를 이분 탐색할 건지 정하는 게 중요하다. 이번에 탐색 데이터를 빠르게 판단하지 못해서 아쉽다.
일반적인 이분 탐색 문제라면 문제에서 반환 또는 출력해야 하는 값에서 힌트를 얻을 수 있을 것 같다. 또한 제한사항이나 조건을 잘 살펴보면 도움이 될 것이다.
나야, 개발자
