[이분탐색] Level 3 입국심사

문제 설명

• n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
• 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
• 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
• 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

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

 

 

입출력 예시 및 설명

 

---

풀이)

 

이 문제는 이분 탐색 알고리즘 자체는 쉬운데 그 알고리즘을 어떻게 적용할지에 대해 고민하는 과정이 꽤나 까다로웠다

그래서 오늘도 Goo교수님과 함께하는 알고리즘 시간..^^*

코드를 보고도 이해하는데 꽤나 오랜 시간이 걸렸다

 

알고리즘은 다음과 같다

심사가 오래 걸리는 심사관 기준으로 심사 시간 배열이 있다고 가정한다

즉, 이분 탐색을 위한 인덱스가 시간이 되는 것이다

start는 1로, end는 (가장 오래걸리는 시간 * 인원수) 로 놓고 여기서 이분탐색을 통해 시간을 줄여나간다

먼저 가운데 시간인 mid를 times 배열로 나눠서 나온 수가 바로 현재 mid 시간으로 검사가 가능한 사람 수이다

이 숫자가 주어진 사람 수보다 크면 시간이 넉넉하단 뜻이니까 줄이기 위해 end를 mid 기준으로 줄이고, 숫자가 사람수보다 작으면 시간이 부족하다는 뜻이니까 start를 mid 기준으로 늘린다

이 과정이 이분탐색이 되는 것이다

원래 이분탐색은 배열의 원소 기준으로 값을 검사하고 인덱스를 옮겼다면, 이 문제에서는 인덱스 자체가 값이 된다

이를 생각하는 과정이 꽤나 까다로운 문제였다

암튼 아래는 코드!!

 

 

 

자바 코드)

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        long start = 1;
        
        Arrays.sort(times);
        long end = (long) times[times.length-1]*n;
        
        while(start<end) {
            long sum=0; //초기화
            long mid = (start+end)/2;
            for(int time : times) {
                sum += mid/time;
            }

            if(sum>=n) {
                end = mid;
            } else {
              start = mid+1;  
            }
        }
        
        answer=start;
        return answer;
    }
}

파이썬에서는 배열의 최댓값을 반환하는 메소드가 있어서 그걸 사용하면 되지만, 자바에는 없어서 times 배열을 정렬하여 가장 큰 값을 얻어오도록 했다.

다른 부분은 위의 알고리즘대로 구현하였다!

 

 

 

파이썬 코드)

def solution(n, times):
    answer=0
    start=1

    end=n*max(times)
    
    answer = binary_search(start, end, n, times)
    
    return answer

# start : 최소 시간
# end : 최대 시간
# mid : 현재 주어진 시간
# sum : mid 시간동안 입국 심사를 받을 수 있는 인원 수 
def binary_search(start, end, n, times):
    while start<end:
        #print("\nstart ",start, "end", end)
        sum=0 #인원 수
        mid=(start+end)//2
        
        for time in times:
            #print(sum, time)
            sum +=mid//time
            
        print("sum",sum)
        if sum>=n: #모든 사람이 입국 심사를 받을 수 있는 경우 -> 시간을 더 줄일 수 있는지 확인하기 위해 시간 배열의 앞에서 검사
            end=mid
        else: # 모든 사람이 받지 못한 경우 -> 시간이 부족한 것이므로 시간 배열의 뒤에서 검사
            start=mid+1
            
    return start

확실히 파이썬이 깔끔하긴 한데 난 자바개발자니까..!

 

 

BBAING