(Python, Java) 프로그래머스 - 입국심사

22 Feb 2022 in Algorithm on Programmers, Level3

[문제 링크]

Python 풀이

def solution(n, times):
    start = 1
    end = max(times) * n

    while start <= end:
        mid = (start + end) // 2

        # 시간이 주어졌을 때 각 심사위원은 몇명을 처리할 수 있는가?
        cnt = 0
        for time in times:
            cnt += mid // time

        if cnt >= n:
            end = mid - 1
            answer = mid
        elif cnt < n:
            start = mid + 1

    return answer

범위를 보자마자 이진탐색이란 것 눈치챘다. 하지만 기준을 세울 수 없었다.
이진탐색이란 것을 눈치챘다면 left, right를 어떻게 선정할 지가 관건이다.
대부분은 문제에서 구하는 답을 기준으로 세우면 된다.
이 문제에서는 최소 시간을 구하는 것이므로 왼쪽은 1, 오른쪽은 모두가 제일 오래걸리는 심사위원에게 받았을 때로 선정하면 된다.

Java 풀이

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        long start = 1;
        long end = (long) (Arrays.stream(times).max().getAsInt()) * n;
        long answer = 0;

        while (start <= end) {
            long mid = (start + end) / 2;

            long count = 0;
            for (int time : times) {
                count += mid / time;
            }

            if (count >= n) {
                end = mid - 1;
                answer = mid;
            } else {
                start = mid + 1;
            }
        }

        return answer;
    }
}