문제: https://school.programmers.co.kr/learn/courses/30/lessons/43238
이분탐색 카테고리에 있는 문제였지만, 이분탐색으로 푸는 방법을 찾기까지 시간이 좀 걸렸다.
'시간의 최소값'에 집중하면, 어떤 순서로 검사받든 가장 최소로 걸리는 시간을 계산하면 되는데,
심사받는 순서에 집중을 하다보니 이분탐색 풀이법이 바로 떠오르지 않았다.
def solution(n, times):
min_val = 1
max_val = max(times)*n
answer = 0
while min_val <= max_val:
mid_val = (min_val+max_val)//2
ans = 0
for time in times:
ans += mid_val//time
if ans >= n:
answer = mid_val
max_val = mid_val-1
elif ans < n:
min_val = mid_val+1
return answer
위 코드로 문제를 해결했다.
먼저 min_val은 문제 조건에 의해 1을 줘도 되고(한명을 검사하는 최소 시간이 1분이고, 입국 심사를 기다리는 사람은 1명 이상이기 때문),
min(times) 값을 줘도 된다. (times 배열의 최소 시간만큼은 걸리기 때문)
max_val은 최대로 걸릴 수 있는 시간 (times 배열의 최대 시간*사람 수)을 지정한다.
min_val이 max_val 보다 작거나 같을 동안 mid_val이 최대 몇명을 수용하는 시간인지 계산한다.
예를 들어 min_val이 1이고 max_val이 60이라고 하자. (문제 예시)
이때 mid_val==20이 된다. 20분의 시간동안 검사받을 수 있는 사람 수(ans)는 7분 2명, 10분 2명으로 총 4명이다.
이는 사람 수인 n값 보다 작으므로 min_val의 값을 mid_val+1로 바꿔서 다시 계산한다.
이러한 과정을 min_val <= max_val인 동안 반복한다.
이때 검사 받을 수 있는 사람 수인 ans 값이 n보다 크거나 같을 때, answer 값을 갱신한다.
처음에는 이 부분이 헷갈려서 아래와 같이 작성했다.
if ans > n:
max_val = mid_val-1
elif ans <= n:
min_val = mid_val+1
answer = mid_val
그런데 이렇게 풀면 완전 오답이다.
왜냐하면 검사 받을 수 있는 사람 수가 실제 사람 수보다 작거나 같을 때 answer값을 갱신하기 때문이다.
검사 받을 수 있는 사람 수가 실제 사람 수 보다 많거나 같아야 현재의 mid_val 시간으로 커버가 가능하다는 의미가 성립한다.
이분탐색 문제를 풀 때 범위 지정에 유의해야할 것 같다.
'코딩테스트' 카테고리의 다른 글
[Python] 프로그래머스 - 섬 연결하기 (0) | 2023.09.02 |
---|---|
[Python] 프로그래머스 - 카펫 (0) | 2023.08.31 |
[Python] 프로그래머스 - 전화번호 목록 (0) | 2023.08.25 |
[Python] 백준 20055번 - 컨베이어 벨트 위의 로봇 (0) | 2023.08.23 |
[Python] 백준 15684번 - 사다리 조작 (0) | 2023.08.23 |