이분탐색을 활용한 알고리즘 문제풀이

오늘 푼 문제: 입국심사

입출력

• 입력: 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어집니다.
• 출력: 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 합니다.

예제 코드

import java.util.*;

class Solution {
    /**
     * 1. 주어진 시간에 심사를 받을 수 있는 사람 = 주어진 시간을 times의 모든 원소로 나눈 값들의 합
     * 2. 범위를 0분 부터 가장 오래 걸리는 심사관에게 모두 받았을때 걸리는 시간을 설정
     * 3. 주어진 시간에 n명보다 더 많이 심사를 받을 경우 시간이 널널하다 -> rt = mid - 1
     * 4. 주어진 시간에 n명보다 더 적게 심사를 받을 경우 시간이 부족하다 -> lt = mid + 1
     * 5. n보다 더 했을 경우 더 적게 걸린 시간을 answer에 할당.
     * Java에서 int의 범위: -2,147,483,648 <= int <= 2,147,483,647
     * Java에서 long의 범위: -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807
     * 왜 answer을 Integer.MAX_VALU로 설정했을까?
     */
    public long solution(int n, int[] times) {
        // Arrays.sort(times);
        long lt = 0L;
        long rt = Arrays.stream(times).max().getAsInt() * (long)n;
        // long answer = Integer.MAX_VALUE;
        long answer = rt;
        while(lt <= rt) {
            long mid = (lt + rt) / 2;
            long tmp = 0;
            // 주어진 시간에 심사를 할 수 있는 사람 수를 구하는 로직
            for (int time : times) tmp += mid / time;
            // n명 이상 할 수 있는 경우
            if (tmp >= n) {
                answer = Math.min(answer, mid);
                rt = mid - 1;
            } else lt = mid + 1; // n명보다 덜 했을 경우
        }
        return answer;
    }
}

• 테스트 케이스가 정수형의 범위를 벗어난다는 걸 늦게 깨달았습니다...!
• 시간에 대해서 lt와 rt를 설정하여 이진탐색을 진행하였습니다.
• lt는 0, rt는 가장 오래걸리는 심사원에서 모두가 심사받을 경우로 초기화합니다.
• 그 후에는 주어진 시간에 심사된 인원에 따라서 lt와 rt를 조정하며 가장 적게 걸린 시간을 찾습니다.
• 이분탐색일 경우 return 값을 살펴보고 upper/lower bound를 결정해야한다.
• Lower Bound: 찾고자 하는 값이 처음으로 나오는 경우
• Upper Bound: 찾고자 하는 값보다 큰 값이 처음으로 나오는 경우

회고

• 테스트 케이스를 유심히 보자!
• 기본에 충실한 개발자가 되자!