99클럽 코테 스터디 13일차 TIL / [프로그래머스] 입국심사

오늘의 학습 키워드

---

이분탐색

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/43238

• 플랫폼: 프로그래머스
• 문제명: 입국심사
• 난이도: Lv3

풀이

---

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        int maxTime = Arrays.stream(times).max().getAsInt();
        
        long left = 0;
        long right = (long)maxTime * n;
        
        while(left <= right) {
            long mid = left + (right - left) / 2;
            
            long passCnt = 0;
            for(int time : times) {
                passCnt += (mid / time);
            }
            
            if(passCnt < n) {
                left = mid + 1;
            } else {
                right = mid - 1;
                answer = mid;
            }
        }
        
        return answer;
    }   
}

접근

• 더 빨리 끝나는 심사대가 있다면 기다렸다가 심사를 받을 수 있다는 조건이 있으므로, 직접 구현한다면 10억의 입력 범위를 시간 내에 풀이하기 어렵습니다.
• 가능한 최대 대기 시간을 구한 뒤, 범위 내에서 이분탐색을 통해 O(logn)에 최소 시간을 도출할 수 있습니다.
  • 가능한 대기 시간의 최대 값은 최대 대기 시간 * n이 됩니다.

    int maxTime = Arrays.stream(times).max().getAsInt();
    
    long left = 0;
    long right = (long)maxTime * n;

  • 이분 탐색에서 mid는 시간을 의미하며, mid만큼의 시간 내에 몇 명이 심사를 받을 수 있는지 확인합니다. 만약 그 수가 n보다 작다면 더 오랜 시간이 필요한 것이고, 반대의 경우는 이미 n명을 만족한 것이니 더 작은 시간 내에 가능한지 확인하면 됩니다.

    while(left <= right) {
        long mid = left + (right - left) / 2;
        
        long passCnt = 0;
        for(int time : times) {
            passCnt += (mid / time);
        }
        
        if(passCnt < n) {
            left = mid + 1;
        } else {
            right = mid - 1;
            answer = mid;
        }
    }

소요 시간

30분

회고

---

값의 범위가 터무니없이 큰 경우 → 복잡도를 줄이기 위한 방법으로 이분 탐색을 고려할 것!