[프로그래머스/Java] 43238 퍼즐 조각 채우기

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

 

🔍  해결 과정

위 문제는 이분탐색의 방식을 활용하여 문제를 해결할 수 있습니다. 문제에서 입국심사에 걸리는 시간의 최솟값을 도출하는 것이 핵심이므로 시간을 기준으로 이분탐색을 위한 과정을 설계해야 합니다. 과정은 다음과 같습니다.

1️⃣ 시간의 최솟값인 leftIdx를 0으로 초기화해준다.
2️⃣ 최대로 오래 걸리는 입국심사 시간을 rightIdx로 초기화해준다. (times의 최댓값을 n명만큼 곱한 값)
3️⃣ 이분탐색의 방식을 활용해 걸릴 수 있는 시간의 중간 값 mid를 생성해주고, mid를 기준으로 입국심사가 가능한 사람 수를 계산한다.
4️⃣ 주어진 n과 비교해가며 적절한 최소 시간을 계속 계산해간다.

 

 

---

✏️ 코드

/**
최소 시간을 리턴해야하므로 시간을 기준으로 세운 다음 이분 탐색을 진행.
**/
class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        long left = 0L; // 최소 시간
        long right = 0L;
        
        for (int time : times) {
            right = Math.max(right, (long) time);
        }
        
        right *= (long) n; // 걸릴 수 있는 최대 시간
        
        while (left <= right) {
            long mid = (left + right) / 2L; // mid가 기준 시간
            long people = 0; // 총 기다리는 사람이 int 범위를 넘어갈 수 있으므로 long 처리
            
            for (int time : times) {
                // 가능한 사람 수를 구하기
                people += mid / time;
            }
            
            if (people >= n) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return answer;
    }
}