프로그래머스 - 이분탐색(입국심사, 징검다리)

문제 링크 - https://programmers.co.kr/learn/courses/30/parts/12486

👀문제이해 및 풀이방법

이번엔 이분탐색이다 예전부터 어려워했던 부분인데 역시나 정말 모르겠다.. 연습양이 부족한것도 있겠지만 어떤값을 찾아나가야할지 보이지를 않는다 좀더 익숙해져야겠다
1번 문제는 모든 사람이 검사를 받는 시간을 생각해서 나올 수 있는 최대값을 right로 최소값인 1을 left로 잡고 각 시간마다 검사할 수 있는 인원을 계산하여 검사할 수 있는 인원이 n보다 큰 가장 작은 값을 찾아내는 문제이다
2번 문제는 바위마다 최소 거리의 가질수있는 최대 거리를 right 최소 거리를 left로 잡고 각 거리마다 없애야 하는 돌의 수를 n으로 잡은 뒤 없애야하는 돌의 수가 n보다 작으면서 최대한 바위마다의 거리 값이 크도록 만드는 골치아픈 문제였다 문제의이해도 어렵지만 이를 잡아내는게 쉽지 않았다
결국 둘다 검색을 통해서 힌트를 알아낸뒤 풀었고 복습이 필요하다

📝코드

1 입국심사

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
long long solution(int n, vector<int> times) {
    sort(times.begin(),times.end());
    long long left=1,right=(long long)times.back()*n;
    long long answer = right;
    while(left<=right){
        long long mid = (left+right)/2;
        long long sol=0;
        for(int i : times)
            sol+=mid/i;
        if(sol>=n){
            answer=min(answer,mid);
            right =mid-1;
        }
        else
            left =mid+1;
    }
    return answer;
}

2 징검다리

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    sort(rocks.begin(),rocks.end());
    int left =0,right=distance;
    int cnt,cur;
    while(left<=right){
        int mid = (left+right)/2;
        cnt=0;
        cur=0;
        for(int i : rocks){
            if(i-cur<mid)
                cnt++;
            else
                cur= i;
        }
        if(cnt<=n){
            answer=max(answer,mid);
            left= mid+1;
        }
        else
            right=mid-1;
    }
    return answer;
}