프로그래머스 알고리즘 고득점 Kit - 이분 탐색

입국심사

- 입국심사를 기다리는 사람 수, 각 심사관의 심사 시간 배열이 주어질 때, 모든 사람이 심사를 받는데 걸리는 최소 시간

- 이진 탐색 문제, 결과론적인 접근 => t만큼의 시간이 지났을 때, 몇 명이 처리되었을까?

- 이진 탐색을 통해 처리된 인원이 n 이상인 t를 구해나가면 됨

#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = (long long)n * (*min_element(times.begin(), times.end()));
    long long l = 1, r = answer;
    
    while(l<=r) {
        long long m = (l+r)/2;
        long long num = 0;
        
        for(int time : times) {
            num += (m/time);
        }
        
        if(num>=n) { // 답의 후보가 될 수 있음
            answer = min(answer, m);
            r = m-1;
        } else {
            l = m+1;
        }
    }
    
    return answer;
}

// 최소 1, 최대는 한 창구에서 모든 손님을 처리했을 때

// answer 구할 때 int*int 연산에서 오버플로우 발생 가능성 있기에 (long long) casting 필수!!

 

징검다리

- distance가 1,000,000,000 이렇게 큰 숫자로 주어지면 이분탐색을 생각해보아야 함

- 조건을 만족하는 (돌 n개 이하를 제거하여 만들 수 있는 최소거리) 거리 값을 구해나가면 됨

int solution(int distance, vector<int> rocks, int n) {
    rocks.push_back(0);
    rocks.push_back(distance);
    sort(rocks.begin(), rocks.end());
    
    int l = 0, r = distance, answer = 0;
    while(l<=r) {
        int m = (l+r)/2;
        
        int dist = 0, removed = 0, minDist = distance;
        for(int i=1; i<rocks.size(); i++) {
            int tmp = rocks[i]-rocks[i-1];
            if(tmp+dist < m) {
                // 돌을 치움 (마지막 idx의 경우 해당 idx를 삭제한다기보다 앞의 돌을 삭제하는 의미)
                removed++;
                dist += tmp;
            } else {
                minDist = min(minDist, tmp+dist);
                dist = 0;
            }
        }
        
        if(removed>n) {
            // 간격을 줄여야 더 적은 돌을 없애고도 조건 만족 가능
            r = m-1;
        } else {
            // n개 이하의 돌을 없애서 minDist 간격 확보 가능
            l = m+1;
            answer = max(answer, minDist);
        }
    }
    return answer;
}

// 매 실행마다 '돌 사이의 최소 유지 간격'인 m을 설정하고

// 해당 간격을 만족하도록 돌을 삭제해나감, 그리고 삭제 결과 돌 사이의 간격들 중 최솟값을 tracing 함

// 마지막 idx에서 tmp+dist<m 인 채로 끝났다는 건 앞의 돌 하나를 더 삭제한다는 의미 (도착지점엔 돌이 없으므로)

// 마지막 idx에서 tmp+dist<m 인 채로 끝났을 때 minDist도 바뀔 가능성이 있어 prevDist 추적하면 좋을 것 같은데 없어도 성공하더라, minDist tracing 안하고 answer = max(answer, m); 해도 답 잘 나옴.

// 어차피 이진탐색으로 조건을 만족하는 가장 최적의 해를 찾아나가기 때문인 듯

// m 거리를 확보하기 위해 n개 이하의 돌을 없애기만 하면 된다 = n개 돌을 없애면 m 거리 확보가 무조건 된다!!