[프로그래머스]이분탐색 : 입국심사 (level 3)(c++, java)

https://programmers.co.kr/learn/courses/30/lessons/43238?language=cpp

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

 

이분탐색

 

c++ 코드

#include <string>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

typedef long long ll;

// t시간 내에 목표한 사람수를 모두 심사할 수 있으면 true 반환
bool possible(vector<int>& times, ll t, int target)
{
    ll passed = 0;
    for (int i = 0; i < times.size(); ++i)
    {
        passed += t / times[i];
    }
    return (passed >= target);
}

ll search(vector<int>& times, ll start, ll end, ll target, ll answer)
{
    // 왼쪽 끝값 > 오른쪽 끝값 일 때, 오른쪽 끝값 반환
    if (start > end)
    {
        return answer;
    }

    // mid값이 충분하면 (=mid시간 내에 주어진 사람수를 모두 심사할 수 있으면)
    // : 오른쪽 끝값을 중간값 - 1로 search 재귀함수 호출
    ll mid = (start + end) / 2;
    if (possible(times, mid, target))
    {
        answer = min(mid, answer);
        return search(times, start, mid - 1, target, answer);
    }
    // mid값이 너무 작으면 : 왼쪽 끝값을 중간값 + 1로 search 재귀함수 호출
    else
    {
        return search(times, mid + 1, end, target, answer);
    }
}

ll solution(int n, vector<int> times) {

    // 오름차순 정렬
    sort(times.begin(), times.end());

    // 주어진 사람 수 n을 전부 심사하는 데에 최소, 최대로 걸리는 시간
    ll low = ((ll)n * times.front()) / times.size();
    ll high = (ll)n * (ll)times.back();

    /*
        이분탐색으로 모든 사람이 심사를 받을 수 있는
        가능한 최소의 시간 구하기
    */
    return search(times, low, high, n, numeric_limits<ll>::max());
}

 

java 코드

class Solution {

    public long solution(int target, int[] times) {

        long left = 0;
        long right = target * (long)getMax(times);
        return getLowerBound(left, right, target, times);
    }
    
    public int getMax(int[] times) {
        int maxTime = 0;
        for (int t : times) {
            maxTime = Math.max(maxTime, t);
        }
        return maxTime;
    }
    
    public long getLowerBound(long left, long right, long target, int[] times) {

        while (left < right) {

            long mid = (left + right) / 2;
            long sum = 0;
            for (int t : times) {
                sum += mid / t;
            }

            if (sum >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }
}

 

 

예산문제와 마찬가지로

조건을 충족하는 가장 근접한 값을 이분탐색으로 구하는 문제였다. 

 

 

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다.
가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다.
하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

문제에서 최종적으로 요구하는 답이 시간이므로,

시간의 최소/최대값을 가지고 이분탐색을 시작해야 한다. 

 

 

어떤 시간 T에서 처리가능한 최대의 사람수는 다음과 같이 구한다.

// times : 심사대별 대기시간 벡터
ll passed = 0;
for (int i = 0; i < times.size(); ++i)
{
    passed += t / times[i];
}

T를 심사대별 대기시간으로 나누면, 각 심사대에서 T시간동안 처리할 수 있는 사람 수가 계산된다.

그 합계가 T시간동안에 전체 심사대가 처리 가능한 사람 수 이다.

 

 

문제에서 주어진 예시를 한번 보자.

int n = 6; 
vector<int> times = {7, 10}; 

// return : 28

첫번째 심사대는 28 / 7 (= 4), 두번째 심사대는 28 / 10 (= 2).

28분동안 총 6명의 사람을 심사할 수 있다. 

 

그런데... 29분도 총 6명의 사람을 심사할 수 있다.

29 / 7 (= 4) +  29 / 10 (= 2) = 6 이기 때문이다.

 

따라서 기존의 단순한 이분탐색 로직으로는 부족하다.

최소가 아닌 T의 값도 반환할 수 있기 때문이다.

// 이 코드는 제대로 작동하지 않는다
ll search(vector<int>& times, ll start, ll end, ll target)
{
    if (start > end)
    {
        return end;
    }

    ll mid = (start + end) / 2;
    ll passed = get_passed(times, mid);

    if (passed == target)	// 위의 예시에서 28이 아니라 29를 반환할 수도 있다.
    {
    	return mid;
    }
    if (passed > target)
    {
        return search(times, start, mid - 1, target);
    }
    else
    {
        return search(times, mid + 1, end, target);
    }
}

 

 

 

 

모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

다시 문제를 참고해서 정리하면

1. T시간 내에 모든 사람이 심사를 받을 수 있어야 한다. --> passed >= target 이면 true

2. T의 최소값을 구해야 한다. --> 1번이 가능한 T의 최소값은 따로 계산하기

 

 

따라서 이분탐색 범위를 결정하는 함수를 bool형으로 바꾸고

모든사람이 T시간 내에 심사가 가능하면

T 최소값을 갱신 한 후, 더 작은 시간범위로 한번 더 이분탐색을 진행한다.

더이상 이분탐색이 가능하지 않을 때 까지!

그 후, 가능한 최소값 T를 반환한다.

// t시간 내에 목표한 사람수를 모두 심사할 수 있으면 true 반환
bool possible(vector<int>& times, ll t, int target)
{
	...
    return (passed >= target);
}

ll search(vector<int>& times, ll start, ll end, ll target, ll answer)
{
    if (start > end)
    {
        return answer;
    }

    ll mid = (start + end) / 2;		// T시간
    if (possible(times, mid, target))
    {
        answer = min(mid, answer);	// 모든사람이 심사 가능할 때 T의 최소값 
        return search(times, start, mid - 1, target, answer);
    }
    else
    {
        return search(times, mid + 1, end, target, answer);
    }
}