[파이썬, Java] 입국심사

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

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

 

입출력 예

n	times	return
6	[7, 10]	28

 

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

출처

 

 

👩‍🦰  나의 풀이

 

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        long max=0;
        for(int m : times) if(m > max) max=m;
        long left=1, right=max*n, mid=0;
        long cnt=0;  // 사람 수
        
        while(left <= right){
            mid=(left+right)/2;
            cnt=0;
            for(int t : times) {
                cnt+=mid/t;
                if(cnt >= n) break;
            }
            if(cnt >= n) {
                answer=mid;
                right=mid-1;
            }else if (cnt < n) left=mid+1;
        }
        return answer;
    }
}

 

이분법 사용

left는 최소 시간 1, right는 모든 고객n이 가장 심사하는데 오래 걸리는 시간으로 초기화한다.

left가 right보다 커질때까지 반복한다.

legt와 rigth는 값의 범위다. 중간값 mid를 찾는다.

cnt+=총심사시간/심사시간을 하면 모든 사람이 심사받는데 걸리는 시간을 구할 수 있다.

cnt가 심사받아야하는 고객 수 n 이상이면 break한다.

cnt가 n 이상이면 최소 총심사시간에 mid를 넣는다. right를 줄여서 총심사시간을 줄인다.

cnt가 n보다 작으면 left를 늘려서 총심사시간이 커지게 된다.

 

 

# 실패
def solution(n, times): # 고객, 각 심사관의 일처리 시간
    answer = 0
    cnt_time=0  
    length=len(times)
    que=[0]*length   # 심사대
    
    while n :
        for i in range(length) :  # 빈 자리에 사람 들어감
            if que[i] == 0 or cnt_time%que[i] == 0 :    # 빈 자리
                que[i]=n 
                n-=1
                cnt_time+=1     # 흐르는 시간    
            cnt_time+=1     # 흐르는 시간
        cnt_time+=1
    return cnt_time+1

 

심사대 que에 값이 0이거나(비었으면) 시간 cnt_time이 심사 시간의 배수면 사람을 넣고 n을 줄였다.

 

 

👸 다른 사람 풀이

 

# 출처 : https://wwlee94.github.io/category/algorithm/binary-search/immigration/
def solution(n, times):		# 고객, 각 심사관의 일처리 시간
    answer = 0
    
    leng=len(times)		# 심사관 수
    left=1
    right=(leng+1)*max(times)       # 최대 범위
    
    while left <= right :
        mid=(left+right)//2
        count=0		# 심사 받은 사람 수
        for time in times :
            count+=mid//time	
            # 심사 인원수를 넘으면 다음 단계
            if count >= n : break
                
        # n명을 심사 할 수 있는 경우
        # 한 심사관에게 주어진 시간을 줄여본다.
        if count >= n :
            answer=mid
            right=mid-1
        # 없는 경우
        elif count < n :
            left=mid+1
    return answer

 

이분탐색을 이용한 풀이

범위가 클 때 이분탐색은 유용하다.

임의로 right의 최대 범위를 정한다.

count는 심사 받은 사람 수다.

총 시간 mid를 심사 시간 time으로 나누면 심사 받는 고객 수를 구할 수 있다.

left가 right보다 더 커지면 반복문이 끝난다.

n명을 심사 할 수 있다면 최대 범위를 줄인다.

n명을 심사 할 수 없다면 최소 범위를 늘린다.

 

 

# 출처 : https://m.post.naver.com/viewer/postView.nhn?volumeNo=27248090&memberNo=33264526
def solution(n, times):
    # 최악의 경우 : 가장 비효율적인 심사관에게 다 받는 경우의 시간
    left, right=1, max(times)*n
    answer = 0
    
    while left <= right :
        # 한 심사관에게 주어진 시간
        mid=(left+right)//2
        people=0
        for i in times :
            # 각 심사관마다 주어진 시간 동안 몇 명의 사람을 심사할 수 있는지
            people+=mid//i
            # 모든 사람을 심사할 수  있으면 반복문을 벗어난다.
            if people >= n :
                break
        # 모든 사람을 심사할 수 있는 경우
        # 한 심사관에게 주어진 시간을 줄여본다
        if people >= n :
            answer=mid
            right=mid-1
        # 모든 사람을 심사할 수 없는 경우
        # 한 심사관에게 주어진 시간을 늘려본다.
        elif people < n :
            left=mid+1
    return answer

 

위랑 알고리즘 같음.

right는 심사 처리 시간이 가장 오래 걸리는 심사관에게 모두 갔을 때이다.

 

 

// https://velog.io/@hyeon930/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC-Java
import java.util.*;
class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        return binarySearch(times, n, times[times.length-1]);
    }
    
    long binarySearch(int[] times, int n, long max){
        long left=1, right=max*n;
        long mid=0;
        long ans=Long.MAX_VALUE;
        
        while(left <= right){
            mid=(left+right)/2;
            
            if(isPassed(times, n, mid)){
                ans=ans>mid?mid:ans;
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        return ans;
    }
    
    boolean isPassed(int[] times, int n, long mid){
        long amount=0;
        
        for(int i=0; i<times.length; ++i){
            amount+=mid/times[i];
        }
        
        if(amount >= n) return true;
        else return false;
    }  
    }

 

이분법 풀이

times를 정렬해서 가장 마지막 값을 binarySearch함수의 max로 준다.

Long.MAX_VALUE는 Long타입에서 표현할 수 있는 최대값이다.

isPassed함수에서는 심사를 받은 사람의 수 amount가 n 이상이면 true를 반환한다.

left를 늘리는 것은 총 심사를 받은 사람의 수 amount가 n보다 작기 때문에 총심사시간을 늘리는 것이다. 

마찬가지로 right는 n 이상이기 때문에 시간을 최소로 줄이기 위해서 줄이는 것이다.

 

 

문제 출처 💁‍♀️ 프로그래머스