99클럽 코테 스터디 13일차 TIL + Programmers 입국 심사대 java

1. 문제 설명

문제 링크

2. 접근 방식

KEY WORD: 이분 탐색

무엇을 기준 으로 이분탐색을 해야할까?

이분 탐색 문제를 풀 때, 제일 어려운 부분이다. 어려운 문제일수록 무엇을 기준으로 이분 탐색을 해야할지 감이 서지 않는다. 나 또한 그랬다. 그래서 다른 사람의 풀이 아이디어까지 봤다. 분명 1년 전에 같은 문제를 백준으로 풀었는데, 안 떠올라서 좀 좌절 했다 ㅜ

(1) 기준 : M 시간 당 각 심사대에서 처리하는 사람의 수

내 기준에서 어려웠던 점은 규칙 - 심사대가 비더라도, 사람은 다른 심사대가 빌 때까지 기다렸다가 들어갈 수 있다. 였다. 이 자율성 때문에, 문제의 유형을 생각하지 못한 것 같다. 하지만 기억해야할 점은, 무엇을 이분 탐색 해야할지 모르겠을 때는, 반환하는 답을 기준으로 탐색할 것이 무엇인지 생각해야 한다는 점이다.

해당 문제는, N 명의 승객이 심사대를 통과하는 최소의 시간을 구하는 문제이다. 그러면 0 ~ 최대로 걸리는 시간 사이를 이분 탐색하면 된다. 다음은 이번 문제의 기준이다.

변수	설명
S	이분 탐색의 왼쪽, 걸리는 시간의 하한선
E	이분 탐색의 오른쪽, 걸리는 시간의 상한선
M	중간값, 한번 체크해볼 걸리는 시간
n	문제에서 주어진 사람의 수
M / times[i]	i번째 심사대에서 M시간 동안 처리하는 사람의 수

M / times[i]의 총합: M시간 동안 심사대에서 처라하는 사람의 수의 총합 (이하 sum(M)으로 표기)

(2) 이분 탐색의 기준

코드	설명
n > sum(M)	M 시간 동안 심사대에서 처리하는 사람의 수가 n명보다 부족하다. S를 높여서 M시간을 높인다.
n <= sum(M)	M시간 동안 처리하는 사람의 수가 n명 이상이다. E를 줄여서 M 시간을 줄인다.

(3) 접근 방식

1. 위에 소개한 변수 S,E를 구하여 M을 매번 구하며 이분 탐색한다.
2. while(S <= E) 로 하면 E가 계속 내려와서 결국 S와 엇갈린다. 이후 S를 반환하면 그것이 답이다.
   (lower bound 이용 -> 이유 4번에서 후술)

3. 코드 분석

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

class Solution {
    // 10^9 -> 시간 복잡도 O(n*log n) 이하로 
    public long solution(int n, int[] times) {
        // 1. 시간이 제일 적게 걸리는 심사대 순으로 정렬 
        // 2. int start, int end 설정 
        // 3. 이분탐색을 통해, 최소로 걸리는 시간 찾기 (출력)
        Arrays.sort(times); 
        return binary_search(0, (long)times[times.length-1] * n, times, n);
    }

    public long binary_search(long start, long end, int [] times, int n) {
        long S = start;
        long E = end;

        while(S<=E){
            // 중간 값 구하기
            long M = (S+E)/2; // 총 걸리는 시간
            // 중간 값을 이용한 다음 행동 계산
            long people = 0;
            for(int i = 0; i< times.length; i++){
                people += M/times[i]; // 각 심사대가 정해진 시간에서 처리하는 사람의 수 
            }
            // 처리하는 사람의 수가 같은 시간(분)에 대해서 제일 최소 시간을 구해야 하므로 lower bound 
            if(people >= n){
                E = M-1;
            }else {
                S = M+1;
            }
        }
        return S;
    }
}

4. 성장하기

(1) sum(M) == n 이어도 탈출하지 않고 E를 줄이는 이유?

sum(M) == n, 즉 M 시간 동안 처리하는 사람의 수가 n인 경우에도 E를 줄이며 이분탐색을 지속하고 있다. 그 이유는 n명을 처리하는 경우의 수 중 최소 시간을 찾기 위해서 이다. sum(M) == n에서 즉시 탈출하면 M이 최소값인지 알 수가 없다. 하지만 해당 경우에도 E를 계속 내리면 결국에 E가 sum(M) < n 인 경우 중 최대값으로 간다. 그리고 S는 sum(M) == n 인 수 중 최소값 위치에 도착한 후 움직이지 않으므로, S와 E가 엇갈리게 되고, 이때 S를 출력하면 답이 된다.