입국심사

• 티어 : Lv. 3
• 정답여부 : 오답
• 알고리즘 유형 : 이분탐색, 매개 변색 탐수

💡문제

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

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

💡입출력 예

💡문제요약

• 모든 사람이 입국심사를 하는데 최솟값의 시간을 구하면 되는 문제

💡알고리즘 설계

• answer : 모든인원이 입국심사를 마치는 최소 시간
• min_time : 가장 적은 시간
• max_time : 모든 인원이 입국심사를 할 때 가장 오래 걸리는 시간
• people : 입국 심사를 마친 사람

1. 입국심사에 걸리는 시간중 가장 적은 시간과 모든 인원이 가장 오래걸린 시간의 값을 넣는다. ex) 만약 입국심사가 10분 걸리는곳에 n명이 다 가면 60분 최대로 오래 걸리는 시간
2. 가장 오래 걸리는 시간과 + 가장 적게 걸리는 시간 중간값을 구해준다.
3. 그 값에서 시간을 나눠주며서 그 시간안에 모든 인원이 심사를 다 했는지 검사한다.
4. 만약 입국 심사가 끝난 사람이 n보다 같거나 큰 경우 answer 값에 넣어주고 더 max_time를 빼서 더 적은 시간을 검사를 끝낸 경우가 있는지 확인한다.
5. 만약 심사를 완료한 인원이 n 보다 작을 경우 min_time +1

💡작성코드

• Java

import java.util.*;
class Solution {
    public long solution(int n, int[] times) {
		long answer = 0;
    int min_time = times[0];
    int max_time = times[times.length-1]* n;
        while(min_time <= max_time) {
			int mid = (min_time + max_time) / 2;
      int people = 0; // 입국 심사 끝난 사람	
			for(int time : times) {
				people += mid / time;
			}
			if (people >= n) {
				answer = mid;
				max_time = mid - 1;
			}
			else {
				min_time = mid + 1;
			}
		}
        return answer;
    }
}

💡시간복잡도

O(logn)

💡틀린 이유 or 수정할 부분

자료형 타입이 long인데 int로 한 바보같은 실수를 했다. 계속 IDE로 구현을 하다보니 어이없는 실수를…

💡틀린 부분 수정 or 다른풀이

• Java

import java.util.*;
class Solution {
    public long solution(int n, int[] times) {
		long answer = 0;
    long min_time = 0;
    long max_time =  (long)times[times.length-1]*(long)n;
        while(min_time <= max_time) {
			long mid = (min_time + max_time) / 2;
            long people = 0; // 입국 심사 끝난 사람	
			for(int time : times) {
				people += mid / time;
			}
			if (people >= n) {
				answer = mid;
				max_time = mid - 1;
			}
			else {
				min_time = mid + 1;
			}
		}
        return answer;
    }
}

💡느낀점 or 기억할 정보

처음에 이분탐색을 기준을 정하는게 어려웠다. 이분탐색 기준을 못 정해 머리를 끙끙 거리다가 어제 코드를 보면서 이해를 했던거 같다. 뭔가 딱 문제와 알고리즘 유형을 제대로 이해를 하면 코드를 구현하는건 어려운게 아닌데 일단 문제가 정말 무슨말인가 싶을때가 ㅁ ㅏㄴ..ㅎ 다..ㅠ 😢