[알고리즘] 프로그래머스 입국심사 -이분탐색- 자바

 

 

 

 

programmers.co.kr/learn/courses/30/lessons/43238?language=java

코딩테스트 연습 - 입국심사

 

프로그래머스 LV3 이분탐색 유형인 입국심사라는 문제를 풀어봤습니다.

 

각자 심사하는데 걸리는 시간이 다른 심사관들이 있는데 N명을 심사하는데 걸리는 최소시간을 구하는 문제입니다.

 

주석에 풀이를 자세히 적어놨고 간략히 설명하면 다음과 같습니다.

1. 걸리는 시간의 최소와 최대를 이분탐색의 left, right로 설정합니다.

2. 이분탐색 시간(mid)을 사용하여 각 심사위원들이 몇명을 처리할 수 있는지(sum) 계산해줍니다. 

3. 걸리는 시간을 계속하여 이분탐색하며 반복문을 돌아주며 최소 시간을 구해줍니다.

 

 

 

 

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);
        long left = 0;
        long right = (long) n * times[times.length - 1]; //가장 최악의 경우의(오래걸리는) 시간
        while (left <= right) {
            long mid = (left + right) / 2;
            long sum = 0; // 총 심사한 인원
            for (int i = 0; i < times.length; i++) { //빨리 심사하는 심사관 순으로 심사처리
                sum += mid / times[i];
            }
            if (sum < n) { // 해야할 인원보다 심사처리 못함 -> 시간 더 필요
                left = mid + 1;
            } else { // 해야할 인원보다 심사처리 많이함 -> 시간을 줄여서 더 최고 경우의 시간을 만든다.
                right = mid - 1;
                answer = mid;
            }
        }
        return answer;
    }
}

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!