[프로그래머스 / Java] 코딩테스트 연습: 입국심사 (이분탐색)

난이도: Level 3

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

프로그래머스

---

 

이분탐색 알고리즘은 알지만 최솟값을 어떻게 이분탐색으로 구해야 할지 감이 잘 잡히지 않았다.

그래서 다른 사람의 풀이를 봤는데, 내가 예전에 백준에서 푼 문제와 유사했다.

풀었던 유형이어도 자주 접하지 않으니까 까먹게 되었다.

 

제한사항

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

입출력 예

n	times	return
6	[7, 10]	28

 

이렇게 데이터가 매우 큰 값으로 주어지면 절대 일반적인 탐색 방법으로는 풀 수가 없고, 이분탐색을 고려해야 한다.

그리고 리턴 값이 28이라는 숫자가 나온다.

이 경우에는 최소 시간을 0으로 설정하고, 최대 시간을 6명의 사람이 모두 심사 시간이 10분씩 걸리는 곳에만 들어가는 최악의 경우로 설정해야 한다.

그렇다면 최대 시간, 즉 최악의 시간은 10(times 배열의 최댓값) * 6(모든 사람 수) = 60이 된다.

이를 코드로 작성하면 다음과 같다.

 

    long answer = 0;    // 모든 사람이 심사를 받는데 걸리는 최소 시간

   

    Arrays.sort(times); // 이분탐색을 위한 배열 오름차순 정렬

   

    long start = 0;     // 가장 최소 시간

    long end = times[times.length - 1] * (long)n;   // 가장 최대 시간

 

 

이분탐색을 위해 배열은 처음에 받았을 때 오름차순으로 정렬해야 한다.

오름차순 정렬되었다면 최댓값은 배열의 가장 끝에있는 값이 되기 때문에 times[times.length - 1]이 된다.

여기서 start와 end의 자료형을 long으로 설정하고, n을 long으로 형변환해주었다.

그 이유는 제한 사항에 적힌 데이터의 숫자가 매우 크기 때문이다.

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

n의 최대 범위는 10억이고, times 배열의 최댓값도 10억인데, 이 경우가 테스트케이스로 들어온다면 

end = times[times.length - 1] * n = 100억이 되어버린다.

int의 최대 범위(약 21억)보다 큰 값이 들어와서 오류가 발생하게 된다.

n을 형변환하지 않는다면 int * int = int로 인식되어서 제대로된 값을 받지 못하게 된다.

start의 초깃값은 0이지만, 이분탐색을 진행하면서 start가 end보다 더 커지게 되므로 start도 long으로 선언해야 한다.

 

start와 end를 설정했으니 이제 이분탐색을 진행하면 된다.

while문을 도는 동안 start와 end의 중간 값인 mid를 계속해서 변환해준다.

현재 시간이 mid일 때를 기준으로 모든 심사관이 심사를 할 수 있는 인원 수를 계산하기 위한 변수 count도 선언한다.

여기서도 mid와 count를 long 타입으로 선언했다.

mid는 start와 end의 중간 값이므로 long으로 반드시 선언해주어야 컴파일 에러가 나지 않는다.

현재 시간이 mid일 때 i번째 심사관은 mid / times[i]명씩 심사를 가능하다.

만약 mid = 10, times = {2, 3, 4}일 때,

0번째 심사관이 mid분동안 심사를 할 수 있는 인원 수 = mid / times[0] = 10 / 2 = 5

1번째 심사관이 mid분동안 심사를 할 수 있는 인원 수 = mid / times[1] = 10 / 3 = 3

2번째 심사관이 mid분동안 심사를 할 수 있는 인원 수 = mid / times[2] = 10 / 4 = 2

모든 심사관이 mid분동안 심사를 할 수 있는 인원 수(count)는 10이 된다.

 

    // 최소 시간이 최대 시간보다 커질 때까지 반복

    while (start <= end) {

        long mid = (start + end) / 2;   // 최소 시간과 최대 시간의 중간 값

        long count = 0;     // 현재 시간이 mid일 때 모든 심사관이 심사를 할 수 있는 인원 수

       

        // 심사관이 한 명을 심사하는 데 걸리는 시간을 모두 탐색

        for (int time : times) {

            // 현재 시간이 mid일 때, 한 명의 심사관은 mid / time명씩 심사 가능

            // 모든 심사관이 심사를 할 수 있는 인원 수(count)에 더하기

            count += mid / time;    

        }

       

       (생략)

 

 

이제 이분 탐색 알고리즘을 이용하는 로직이다.

 

1) 모든 심사관이 mid분동안 심사를 할 수 있는 인원 수(count)가 모든 사람 수(n)미만이라면, mid분일 때는 모든 사람(n)을 심사할 수가 없다.

그렇다면 mid분보다 더 많은 시간이 주어지면 더 많은 사람을 심사할 수 있을 것이다.

start = mid + 1을 해서 시간을 늘려준다.

이것이 바로 이분탐색을 쓰는 이유이다.

시간을 1분씩만 찔끔찔끔 늘려주면 10억분이라는 시간을 탐색하는 데에는 너무 오래 걸린다.

반면 start = mid + 1을 해주면 시간을 늘려주는 범위가 커서 10억분을 탐색하는 시간을 훨씬 줄여준다.

 

2) 모든 심사관이 mid분동안 심사를 할 수 있는 인원 수(count)가 모든 사람 수(n)이상이라면, mid분일 때는 모든 사람(n)을 심사할 수 있다.

일단 모든 사람이 심사를 받는데 걸리는 최소 시간인 answer를 mid로 설정해준다.

mid분보다 더 적은 시간이 주어지면 그 전보다 더 적은 사람을 심사하면서 모든 사람(n)을 심사할 수 있을 것이다.

즉, 만약 모든 사람의 수가 3명(n = 3)인데 6명을 심사한 경우(count = 6)의 mid보다는 4명을 심사한 경우(count = 4)의 mid가 더 작은 값이 되므로, 4명을 심사한 경우의 mid가 자동적으로 최솟값이 된다.

6명을 심사하나 4명을 심사하나 둘 다 모든 사람의 수인 3명을 심사했기 때문이다.

이게 자동적으로 최솟값이 설정되는 이유는 이분탐색을 하면서 탐색 범위를 점점 좁혀가기 때문이다.

 

start가 end보다 커진다면 while문을 빠져나오고, 최종적으로 answer(모든 사람이 심사를 받는데 걸리는 최소 시간)를 리턴하면 된다.

 

    // 최소 시간이 최대 시간보다 커질 때까지 반복

    while (start <= end) {

        (생략)

       

        // 심사를 할 수 있는 인원 수가 입국 심사를 기다리는 모든 사람 수(n) 미만이라면

        // 현재 시간이 mid일 때는 모든 사람(n)을 심사할 수 없음

        if (count < n) {    

            start = mid + 1;    // 더 많은 사람을 심사할 수 있도록 시간을 늘리기

        } else {   // 심사를 할 수 있는 인원 수가 입국 심사를 기다리는 모든 사람 수(n) 이상이라면

            // 현재 시간이 mid일 때는 모든 사람(n)을 심사할 수 있음

            // mid가 더 작은 값이 들어올 수도 있음

            answer = mid;      

            end = mid - 1;      // 모든 사람을 심사하는 최소 시간을 찾기 위해서 시간을 줄이기

        }

    }

   

    return answer;  // 모든 사람이 심사를 받는데 걸리는 최소 시간 리턴

 

---

전체 코드

import java.util.*;
 
class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;    // 모든 사람이 심사를 받는데 걸리는 최소 시간
        
        Arrays.sort(times); // 이분탐색을 위한 배열 오름차순 정렬
        
        long start = 0;     // 가장 최소 시간
        long end = times[times.length - 1] * (long)n;   // 가장 최대 시간
        
        // 최소 시간이 최대 시간보다 커질 때까지 반복
        while (start <= end) {
            long mid = (start + end) / 2;   // 최소 시간과 최대 시간의 중간 값
            long count = 0;     // 현재 시간이 mid일 때 모든 심사관이 심사를 할 수 있는 인원 수
            
            // 심사관이 한 명을 심사하는 데 걸리는 시간을 모두 탐색
            for (int time : times) {
                // 현재 시간이 mid일 때, 한 명의 심사관은 mid / time명씩 심사 가능
                // 모든 심사관이 심사를 할 수 있는 인원 수(count)에 더하기
                count += mid / time;    
            }
            
            // 심사를 할 수 있는 인원 수가 입국 심사를 기다리는 모든 사람 수(n) 미만이라면
            // 현재 시간이 mid일 때는 모든 사람(n)을 심사할 수 없음
            if (count < n) {    
                start = mid + 1;    // 더 많은 사람을 심사할 수 있도록 시간을 늘리기
            } else {   // 심사를 할 수 있는 인원 수가 입국 심사를 기다리는 모든 사람 수(n) 이상이라면 
                // 현재 시간이 mid일 때는 모든 사람(n)을 심사할 수 있음
                // mid가 더 작은 값이 들어올 수도 있음
                answer = mid;       
                end = mid - 1;      // 모든 사람을 심사하는 최소 시간을 찾기 위해서 시간을 줄이기
            }
        }
        
        return answer;  // 모든 사람이 심사를 받는데 걸리는 최소 시간 리턴
    }
}