Today I Learned
오늘은 이진 탐색 문제를 풀어보았다. 발상이 힘든 문제여서 계속 고민을 하고, 힌트를 보면서 겨우 풀어낸 문제였다. 코드는 쉬웠지만 머리속으로 생각을 많이 해야되는 좋은 문제였다.
입국심사
문제
입국 심사를 기다리는 사람 n 명이 있다. times 배열에는 각 심사관들이 심사에 걸리는 시간이 담겨 있다. 처음엔 모든 심사대가 비어있고, 한 심사대에는 한 사람만 심사가 가능하다. 모든 사람이 심사를 다 받는 최소 시간을 구하라.
풀이 과정
이진 탐색에 대한 내용은 TIL #116에 정리해두었다.
-
이진 탐색을 활용해 최소 시간을 빠르게 구할 수 있다.
-
결국 시간을 구해야 되는 문제이므로 start, end, mid 모두 시간으로 간주하고 변수를 만든다.
-
우선 정렬을 한 뒤 start는 가장 적은 시간이 걸리는 심사관 1명의 시간(최소 시간), end는 가장 오래 걸리는 심사관이 모든 사람을 심사했을 때의 시간(최대 시간)으로 초기화한다.
=> 이진탐색이라서 우선 정렬부터 하고 봤는데 생각해보니 mid값은 times 배열을 탐색하는 것이 아니므로 정렬을 할 필요가 없다. start 최소값은 1로 하고 최대값만 stream을 써서 max값을 뽑아서 end에 할당했다. O(n log n)의 정렬과정이 사라지고 O(n)만 생기므로 시간복잡도 측면에서 효율적이다. -
while(start<=end)로 이진탐색에 쓸 while문을 만든다. mid는 start와 end의 중간값으로 이번 차례에서 심사하는데 걸리는 총 시간이고, sum은 총 검사할 수 있는 사람의 수이다.
-
mid 값을 각 심사관들의 시간으로 나누면 그 시간동안 검사할 수 있는 총 사람의 수가 나온다. 이 값이 n보다 작으면 mid 시간동안 검사를 다 수행할 수 없다는 뜻이다. 고로 start값을 mid +1로 올려 이진탐색으로 범위를 줄인다.
-
반대로 sum이 n보다 크면 mid 시간동안 n명을 다 검사할 수 있다는 뜻이다. 즉, 좀 더 시간을 줄일 수도 있으니 end를 mid -1로 내려 이진 탐색으로 범위를 줄여 다시 수행한다. 이때의 mid값은 최소값일 수 있으니 일단 answer에 저장해둔다.
-
위의 과정을 통해 이진 탐색으로 n명을 검사하는데 걸리는 최소 시간을 구할 수 있다.
구현 코드
import java.util.*;
class Solution {
public long solution(int n, int[] times) {
long answer = 0;
long start = 1;
int max = Arrays.stream(times).max().getAsInt();
long end = (long) max * n;
long mid, sum;
while(start <= end){
mid = (start + end) / 2;
sum = 0;
for(int t : times){
sum += mid/t;
}
if(sum < n) {
start = mid + 1;
} else {
end = mid - 1;
answer = mid;
}
}
return answer;
}
}알게된 점
-
코드는 쉽지만 발상이 힘든 문제였다. 이진 탐색이라는 꼬리표가 안달려 있었으면 이진 탐색으로 풀 생각을 못했을 것 같다. 다양한 문제를 접하면서 이런 경우는 이렇게 풀면 된다는 경험을 쌓는 것이 중요해 보인다.
-
결국 반환값이 가장 중요하다. 이 문제에서도 어떤 순서로 사람들을 심사관들에게 배치할까 라는 사고방식으로는 풀기 힘들다. 결국 최소 시간을 구해야 하는 문제이기 때문에 시간을 늘리고 줄여가면서 이 시간동안 사람들을 다 심사할 수 있는지 검증해보며 최소 시간을 찾는 방식으로 풀면 쉽게 풀린다. 문제를 풀 때 접근 방식에 대해 잘 생각해보고 풀자!
-
n은 int기때문에 (long) 을 앞에 붙여 형변환을 해주고 곱해야 한다.
