알고리즘) 프로그래머스 BinarySearch, 입국심사

프로그래머스 고득점 Kit - Binary Search(이분 검색, 이진 검색)

입국심사

프로그래머스

풀이

이분 검색에 대한 이해가 완전히 되지 않아서 다른 분들의 로직을 보고, '아! 이렇게 하는거였지' 느꼈다.. 갈길이 아직도 멀다... 

제한사항

입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.심사관은 1명 이상 100,000명 이하입니다.

제한사항을 따로 적은 이유는 주로 데이터 타입과 대략적인 로직이 잡히기 때문이다. 위의 문제는 long형 변수와 loop의 최소화가 필요하다는 것을 보여준다. 하지만, 내 머리로는 Big(O)를 더 줄이는 방법을 아직 모르겠다..

아무튼 코드의 로직을 보자면,

1. 문제의 정답이 최소 입국심사 시간을 return 하는 것이기 때문에 이진 탐색에 필요한 변수는 시간을 다룬다.

2. 중간 값을 return되는 답이라고 가정하고, 이 시간동안 입국심사를 할 수 있는 인원 수를 구해준다.

  => 심사관별로 중간값(가정 답) / 심사시간 ~> 심사관마다 입국심사를 진행할 수 있는 인원

3. 심사한 사람의 수와 주어진 사람 수 n을 비교하여 left와 right를 움직여준다.

 

코드

import java.util.Arrays;

public class KitBinarySearchImmigration {
    private static long solution(int n, int[] times) {
        Arrays.sort(times);

        return binarySearch(n, times, times[times.length-1]);
    }
    private static long binarySearch(int n, int[] times, long maxTime) {
        // 시간 범위
        long left =1;   // 1분 부터
        long right = maxTime*(long)n; // 최대 걸리는 시간 (가장 느린 심사관)

        while(left < right) {
            long mid = (left+right)/2;  // 걸리는 시간 범위의 중간값을 찾아주고
            long people = getPeople(times, mid);    // 이 시간이 몇명의 사람을 수용하는지 받아와준다.
            if(people < n) {    // 심사한 사람의 수가 n보다 작을 때
                left = mid+1;   // 시간을 더 잡아주기 위해서 left를 mid+1로 설정
            } else {            // 시간이 여유로워서 사람을 n보다 더 많이 심사했으면
                right = mid;    // 최대 시간 범위를 mid로 줄여준다.
            }
        }
        return left;
    }

    private static long getPeople(int[] times, long mid) {    // 모든 창구에서 걸리는 최대 시간 리턴
        long result =0;
        for(int time : times) {
            result += mid/time;
        }
        return result;
    }

    public static void main(String[] args) {
//        int[] times = {7, 10};
//        int[] times = {8, 10, 3};
//        int[] times = {1, 10};
        int[] times = {1, 10, 3 ,20, 7, 6};
//        int[] times = {1000000000, 1000000000, 1000000000};
        int n =100;

        System.out.println(solution(n,times));
    }
}