(프로그래머스 C++) 입국심사

문제 링크 : programmers.co.kr/learn/courses/30/lessons/43238#

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

분류 : 이분 탐색

---

처음에는 왜 이분 탐색으로 문제가 분류되어있는지 이해가 안갔다. 

완전탐색(Brute Force)으로 도전하려했는데, 생각해보니 입력 값의 범위가 10억까지 가능해서 분명 시간초과가 날 것이 예상되었다. 그러다가 이분 탐색의 공식 근본 자체를 생각해보니, 이분 탐색 문제가 맞음을 파악했다.

(정답을 구하기 위한) 추정 시간 값 / 심사담당자 별 소요 시간 = 각 심사 담당자가 맡을 수 있는 입국자 수

이분 탐색에 근거하여 위의 추론을 세운 뒤, 도출해낸 결과값이 목표 입국자 수 n을 달성하냐 못하냐에 따라 left, right값을 변경해주면 된다.

 

문제 풀이는 다음과 같다.

1. 이분 탐색의 조건은 배열이 오름차순으로 정렬되는 것이다. 때문에 times 배열을 먼저 정렬해준다.

2. left(최소값)은 0 혹은 1로 세운다.

최소 입국자 수가 1명이고 최소 심사원의 수가 1명이니 최소값을 1로 세워도 무방하지만, 편의상 나는 0으로 세웠다. 

3. right(최대값)은 times의 마지막 값 * 인원수로 세워준다. 

이는 모든 사람들을 심사하는데 가장 오랜 시간이 걸리는 경우를 의미한다.

여기서 주의해야할 점은, 각 계산식에 (long long) 형변환을 해줘야 한다는 점이다. 만약 빠트릴 경우 일부 테스트 케이스(특히 8번과 15번)에서 범위가 초과하여 실패할 수도 있다.

4. 중간 값은 left와 right의 합의 1/2로 세워준다. 이는 (정답을 구하기 위한) 추정 시간 값을 의미한다. 

그렇게 추정 시간값 / 심사당당자 별 소요 시간을 더해주면 해당 심사 대비 전체 심사 가능한 인원수가 도출된다.

5. 심사 가능한 인원수가 목표값 n보다 작으면 left(최소값)을 mid + 1로 설정해준다.

6. 반대로 심사 가능한 인원수가 목표값 n보다 크면 더 작은 시간 또한 고려할 수 있다는 의미이므로,

right(최대값)을 mid -1로 설정해준다. 

7. 6번과 동시에 mid값이 answer보다 작으면 해당 mid를 answer로 저장해준다. 

 

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0, le=0, ri=0, mid=0;
    ri = (long long)times[times.size()-1] * (long long)n; // 주의
    answer = ri;
    while(le<=ri){
        long long temp = 0;
        mid = (le+ri)/2;
        for(int time : times) temp += mid/time;
        if(temp<n) le = mid+1;
        else{
            if(answer>mid) answer = mid;
            ri = mid-1;
        }
    }
    return answer;
}