[프로그래머스/Level3] 입국 심사 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 이분 탐색

1. times 배열을 오름차순 정렬한다.

2. left는 0으로, right는 times 배열의 마지막 원소 * 사람 수로 정한다.

3. left <= right일 때까지 이분 탐색한다.

     1) (left+right)/2 한 값인 mid 시간을 구한다.

     2) 반복문을 통해 해당 시간으로 총 몇 명을 심사할 수 있는지 계산한다.

long cnt = 0;  // 심사한 총 사람 수

for(int i = 0 ; i < times.length ; i++) {
    cnt += mid / times[i];
}

 

     3) 총 심사 인원이 사람 수 n보다 적다면, 모든 사람을 심사할 수 없으므로 left를 mid + 1 값으로 이동시킨다.

     4) n보다 크거나 같다면, 모든 사람을 심사할 수 있으므로 right을 mid - 1로 이동해 탐색 범위를 줄이고, answer에 mid를 넣어둔다. (나중에 더 최솟값이 나올 수 있긴 함)

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;    // 모든 사람이 심사 받는 데 걸리는 시간의 최솟값
        
        Arrays.sort(times);
        
        long left = 0;
        long right = times[times.length -1] * (long)n;  // 모든 사람이 가장 느리게 심사 받는 시간
        
        while(left <= right) {
            long mid = (left + right) / 2;
            long cnt = 0;  // 총 심사한 인원
            
            for(int i = 0 ; i < times.length ; i++) {
                cnt += mid / times[i];
            }
            
            if(cnt < n)    // 해당 시간 동안 모든 사람 검사할 수 없으므로 시간 더 필요
                left = mid + 1;
            else {  // right 범위 줄이기
                right = mid - 1;
                answer = mid;
            }
        }
        
        return answer;
    }
}

 

 

---

💦 어려웠던 점

- 이분 탐색 right의 초기값 설정을 무작정 times의 가장 큰 원소로 할 뻔했다.

- 매 범위마다 총 심사 가능한 인원 수를 구하고, 이 숫자를 n과 비교해 활용할 생각을 하지 못 했다. (저 for문 만들 생각은 했는데 그 다음에 멍..하였다..)

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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

 

[알고리즘] 프로그래머스 입국심사 -이분탐색- 자바