[프로그래머스] Lv.3 입국 심사

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

프로그래머스

 

문제 접근 방법

1. n의 값이 10억, 시간도 10억까지 허용 가능하므로 long 타입으로 계산을 해야한다.

2. 이분 탐색에서 max 값은 최악의 케이스를 가정한다.

  2-1. mid값은 (min + max) / 2로 계산한다. 

  2-2. times를 돌면서 long 타입의 tmp에 (mid / times[i])를 더해준다. 여기서 계산된 tmp는 mid(총 시간)에 처리 가능한 사람 수                라고 보면 된다.

  2-2. tmp값이 n보다 같거나 크다면, max 값을 mid - 1로 설정해주고, answer = mid로 선언해준다.

  2-3. tmp값이 n보다 작다면, 총 시간을 늘려줄 필요가 있으므로 min = mid + 1로 설정해준다.

 

import java.util.*;
class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        Arrays.sort(times);
        long min = 1;
        long max = times[times.length - 1] * (long)n;
        
        while (min <= max) {
            long mid = (min + max) / 2; // 시간 
            long tmp = 0;
            
            for(int i = 0; i < times.length; i++) {
                tmp += (mid / times[i]);
            }
           
            if (tmp >= n) {
                max = mid - 1;
                answer = mid;
                //System.out.println(mid);
            }
            else min = mid + 1;
                        
        }        
        return answer;
    }
}

 

 

문제 풀이 회고

 

이분 탐색인 것을 처음에 전혀 캐치하지 못했었다. 걸리는 총 시간의 최악의 케이스를 기준으로 잡고 풀이를 하니, 어느정도 이해가 됐다.

 

6번 테스트 케이스 실패

while문에서 기존에는 min < max와 같이 두 값이 동일한 경우를 고려하지 않았는데 6번만 실패했다. 

 

n = 59, times=[1,1]
answer=30

이 케이스일 때 실패한다.