입국심사 - 프로그래머스 LV3 JAVA

문제 설명

 

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

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

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

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

 

 

제한사항

 

입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.

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

심사관은 1명 이상 100,000명 이하입니다.

 

입출력 예

 

n	times	result
6	[7, 10]	28

 

---

 

 

이분탐색 몰랐을 때

---

출력값 = 최적의 시간

결국 n==0이 됐을 때의 시간을 구해야 했기 때문에

while문을 사용, while문 조건을 n!=0으로 두고 세부조건을 while문안에 넣었다

 

→ 코드의 성능문제로 시간초과되었다. 코드 성능이라는 것을 고려해야 되는 것을 처음 깨달았다

// 배열 길이 = 심사관 수
// while문안의 사람 수가 0이되면 그만 돌리고
// 걸리는 시간은 answer에 담아서 ++
// answer이 1씩 올라가면서 arrNum%answer=0이되면 사람수 -- 

double solution(double n, double[] times){
		double answer = 0;
		double timeslength = times.length;
		while(n!=0) { // 사람수가 0이되면 종료
			answer ++;
			for(int i=0; i<timeslength; i++) {   
				if(answer%times[i]==0) { 
					n--;
				}
			}			
		}
		
		return answer;		
}

 

 

 

 

 

이분탐색(이진탐색) Binary Search

---

정렬되어 있는 리스트에 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

배열 내부의 데이터가 정렬되어 있어야만 사용 할 수 있다

변수 3개를 사용하여 탐색하며 찾으려는 데이터와 중간에 있는 데이터를 반복적으로 비교, 원하는 데이터를 찾는 과정

 

public long solution(int n, int[] times) {
    long answer = 0;
    Arrays.sort(times);
    long left = 0;
    long right = (long) n * times[times.length - 1]; //가장 최악의 경우의(오래걸리는) 시간
    while (left <= right) {
        long mid = (left + right) / 2;
        long sum = 0; // 총 심사한 인원
        for (int i = 0; i < times.length; i++) { //빨리 심사하는 심사관 순으로 심사처리
            sum += mid / times[i];               // //시간이 mid만큼 주어졌을 때 심사 통과 수               
        }
        if (sum < n) { // 해야할 인원보다 심사처리 못함 -> 시간 더 필요
            left = mid + 1;
        } else { // 해야할 인원보다 심사처리 많이함 -> 시간을 줄여서 더 최고 경우의 시간을 만든다.
            right = mid - 1;
            answer = mid;
        }
    }
    return answer;
 }