99클럽 코테 스터디 3일차 TIL

프로그래머스 - 입국심사

넘어가자

---

문제 이해

• n명의 사람이 입국 심사를 위해 대기 중
• 입국 심사대는 여러 개가 있고, 각 심사관마다 한 명을 처리하는 데 걸리는 시간이 다르다.
• 모든 사람이 심사를 마치고 입국하는 데 걸리는 최소 시간을 구해야 한다.

핵심은 특정 시간 동안 몇 명의 사람이 심사받을 수 있는지 계산하며 시간을 좁혀가야 한다.

 

그렇다면 특정 시간은 어떻게 지정해야 할까. 

각 심사관이 한 명을 심사하는 데 걸리는시간은 1 <= time <= 1,000,000,000이다.

가장 느림 심사관이 모든 인원을 처리하는 경우를 최대 시간으로 잡는다면 (1,000,000,000 * n명) 시간이 된다.

 

이분탐색을 활용하여 중간시간을 계산하고, 그 시간 동안 각 심사관이 몇 명을 처리할 수 있는지 계산해야 해 보자.

처리 가능한 인원수(totalPeople)가 n명 이상이면 시간을 줄이고, n명 미만이면 시간을 늘려야 하다.

static long solution(int n, int[] times) {
    long left = 0;
    long right = (long) (1e9 * n);
    long answer = right;

    while (left <= right) {
        long mid = (left + right) / 2;

        long totalPeople = 0;
        for (int time : times) {
            totalPeople += (mid / time);
            if (totalPeople >= n) break; // n명을 넘은 경우 더 계산할 필요가 없다.
        }

        if (totalPeople >= n) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return answer;
}

---

지금까지의 이분탐색을 활용하는 문제를 살펴보면

• 게임 : 최소 몇 번 더 해야~
• 징검다리 : 밟은 수 있는 징검다리의 최대 수
• 입국심사 : 걸리는 시간의 최솟값 

특정 범위 내에서 최대/최소 값을 구하라는 내용이 나왔다.

그리고 1일 차, 2일 차 문제풀이를 다시 보니 풀이 형식이 굉장히 비슷했다.

long result = 결과값;
long left = 최소 범위;
long right = 최대 범위;

while (left <= right) {
    // 중간 값 계산
    long mid = (left + right) / 2;

    /**
     * 중간 값을 활용한 계산(특정 값 A)
     * 1. 게임 - 승률 구하기
     * 2. 징검다리 - 등차수열의 합
     * 3. 입국심사 - 심사관 최대 심사인원 수
     */

    if (A와 입력값(n) 조건 비교) {
        result = mid;
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}

다음 이분탐색 문제는 이 프로세스를 가지고 풀어보자.

 

프로그래머스 - 입국심사

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