프로그래머스 Lv.3 입국심사와 이진탐색

해결하지 못하여서 구글링하였다.
나는 완전탐색, 그리디, 이진탐색 문제들에 약한 것 같다.

입국심사

def solution(n, times):
    answer = 0;
    left,right=1,max(times)*n; # left는 최소시간 right는 최대시간
    while(left<=right):
        mid=(left+right)//2;
        people=0;
        for time in times:
            people += mid //time; # mid 시간동안 심사한 사람의 수

            if people>=n:
                break;

        # 검사할 수 있는 사람이 검사할 사람보다 많을 경우

        if people >= n:
            answer =mid;
            right = mid - 1;

        # 검사할 수 있는 사람이 검사할 사람보다 적을 경우

        elif people<n:
            left = mid + 1;

    return answer;

로직은 다음과 같다.

1. 최소시간(left)과 최대시간(right)을 정한다.
2. 중간값인 (mid)시간에는 몇 명 검사할 수 있는지 검사한다.
   즉 mid를 기준으로 삼는다.
3. n명 검사할 수 있을경우 right를 mid-1로, n명을 다 검사하지 못할 경우 left를 mid+1로 한다.

이는 mid값을 기준으로 각각의 경우에 해가 되는 right값은 mid의 왼쪽, 해가 되는 left값은 mid의 오른쪽에 위치하기 때문이다.

4. right가 left보다 작아질 때 까지 반복한다.
   최대시간(right)이 최소시간(left)보다 작아졌다는 것은 이전 시행의 결과가 해라는 의미이다.

이진탐색

이진탐색은 기준을 정해놓고 범위를 줄여나가는 것이 핵심인 것 같다.

이 문제의 경우 n명을 검사해야 하므로 n명을 검사할 수 있는 범위를 구해 기준으로 하고 범위를 줄여나가는 방식으로 풀어야 했다.

정리

나와는 상성이 좋지 않지만 비슷한 유형의 문제를 풀다보면 풀 수 있을 것이라고 생각한다..!