99클럽 코테 스터디 20일차 TIL, 이분법(입국심사)

1. 문제 정의

2. 문제 접근

처음에는 queue를 사용하여 각각의 심사대를 queue로 정의해서 빼려고 했으나 그럼 공간복잡도가 너무 많이 나올 것 같아서 찾아보니 이분법으로도 해결이 가능해 보였다.

3. 문제 풀이

1. 두 포인트를 지정한다.
2. 두 포인트의 중앙을 구하여 몇명이 통과 가능한지를  정한다.
3. 계속 범위를 좁혀나간다.

4. 코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);
        long l = 0;
        long r = times[times.length-1] * (long) n; // 모든 사람이 다 천천히 받을 때
        
        while(l <= r){
            long mid = l + (r-l)/2;
            long complete = 0;
            for(int i = 0; i < times.length; i++){
                complete += mid / times[i];
            }
            
            if(complete < n){ // 모든 사람이 제시간안에 다 심사를 받는다.
                l = mid + 1; 
            } else { // 모든 사람이 다 심사를 받지만, 더 최솟값이 있을 수도 있다.
                r = mid - 1;
                answer = mid;
            }
        }
        
        return answer;
    }
}

 

 

 

5. 회고

처음에는 Queue로 해보려다가 공간복잡도가 너무 올라갈 것 같아서 포기했다. 실제로 이런 알고리즘이 입국심사대에 이용하고 있을지도 모른다는 생각이 들었다.