99클럽 코테 스터디 3일차 TIL : 이분탐색

 

문제

프로그래머스 입국심사  | LEVEL 3

#이분탐색 #수학

https://school.programmers.co.kr/learn/courses/30/lessons/43238

 

풀이 & 코드

* 각 심사관 별 심사시간이 담긴 times 배열 오름차순 정렬

    * left = 0초(최소)

    * right = times[times.length-1] * (long) n 초 (최대 n명 * 가장 오래걸리는 시간)

 

* 이분탐색 while로 진행

    * mid = left + right / 2

    * mid일때, 각 심사대 별로 주어진 시간동안 몇명 심사할 수 있는지 count

      ex) mid = 30 times[7,10] ⇒ 30/7 + 30/10 = 7

 

* count한게 n보다 작을 경우 = answer가 더 클것

   * left = mid + 1

 

* count한게 n보다 크거나 같을 경우 = answer가 더 작을 것

   * right = mid - 1

   * 이때, answer는 mid로 일단 넣어두고, while 돌면서 최적 값 찾기

import java.util.*;
import java.io.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        Arrays.sort(times);
        long left = 0;
        long right = times[times.length-1] * (long) n; // 60초 (최대 n명 * 가장 오래걸리는 시간)
        
        while(left <= right){
            long mid = (left + right) / 2;
            
            long peopleCnt = 0;
            for(int time : times){
                peopleCnt += mid/time;
            }
            
            if(peopleCnt < n){
                left = mid+1;
            } else {
                answer = mid;
                right = mid-1;
            }
        }

        return answer;
    }
}

 

회고 & 배운점

* 이분탐색 공부 (https://www.notion.so/dev-if/12430ed61f7880e4bff9c318f2e6f7c4)

* 선형탐색과 이분탐색의 속도 차이 

   * 선형탐색 : O(n) 

   * 이분탐색 : O(log n) → 리스트가 정렬되어 있으며, 검색 범위를 반으로 줄임