이분탐색(Binary Search)

이분 탐색(이진 탐색) : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

• 이분 탐색은 배열 내부의 데이터가 정렬되어야만 사용할 수 있는 알고리즘

• 찾으려는 데이터와 중간 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는것

  

프로그래머스 : 입국심사

이분탐색으로 어떤식으로 접근해야할 지 모르겠어서 찾아가보면서 풀었다.

1. 심사 시간이 담긴 times 배열을 오름차순으로 정렬
2. start = times[0], end = times[times.size()-1] * n
3. 이분 탐색
   • mid를 구한다. (mid = (start + end)/2)
   • 주어진 mid 시간 동안 몇명의 사람을 심사할 수 있는지 합산한다.
     (mid = 30, times = {7, 10}이면, 30/7 + 30/10 = 7명 심사 가능)
   • 심사 가능한 총 사람의 수가 n보다 작으면 start = mid + 1로 하고 다시 이분탐색
   • 심사 가능한 총 사람의 수가 n보다 크거나 같으면 mid의 값을 따로 저장해두고 end = mid - 1하고 다시 이분 탐색
   • 만약 start > end가 되면 이분탐색 종료

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

using namespace std;

long long binary_search(int n, vector<int> times){
  //초기 start와 end 값 정하기
  long long start = times[0];
  long long end = (long long)times[times.size()-1]*n;
  //시간 최솟값 정할 변수
  long long result;
  while(start <= end){
    long long mid = (start + end)/2;
    //심사가능한 총 인원 저장할 변수
    long long count = 0;
    for(int i=0;i<times.size();i++){
      count += mid/times[i];
    }
    if(count < n){
      start = mid + 1;
    } else{
      result = mid;
      end = mid - 1;
    }
  }
  return result;
}

long long solution(int n, vector<int> times){
  //times 오름차순으로 정렬
  sort(times.begin(),times.end());
  long long answer = binary_search(n, times);
  return answer;
}

int main(void){
  int n = 6;
  vector<int> times = {7,10};
  long long result = solution(n, times);
  cout<<result<<'\n';
}