[Java] 프로그래머스 입국심사 (이진탐색)

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43238?language=java# 

코딩테스트 연습 - 입국심사

 

 

 

 

접근 방법

이분탐색으로 푸는 문제인데 형변환에 주의해야 한다.

처음에는 아래와 같이 우선순위 큐로 풀었는데 시간초과가 떴다.

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        int len = times.length;
        
        PriorityQueue<Long> pq = new PriorityQueue<Long>();
        
        for(int i = 0; i<len; i++){
            for(int j = 1; j<=n; j++){
                pq.add((long)times[i]*j);
            }
        }
        long cnt = 0;
        while(!pq.isEmpty()){
           cnt += 1;
            long num = pq.poll();
            //System.out.println(num);
            if(cnt==n){
                answer = num;
                break;
            }
        }
        
        return answer;
    }
}

 

 

그래서 이분 탐색으로 해결하였다.

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        
        int len = times.length;
        Arrays.sort(times);
        
        long maxi = (long) times[len-1] * n;		//여기서 형변환 안 하면 틀림.
        long answer = maxi;
        
        long left = 1;
        long right = maxi;
        while(left<=right){
            long mid = (left+right)/2;
            
            long sum = 0;					//sum 도 long 으로!
            for(int i = 0; i<len; i++){
                sum += mid/times[i];
            }

            if(sum>=n){
                if(mid < answer){
                    answer = mid;
                }
                right = mid - 1;
            } 
            else left = mid + 1;
            
        }

        return answer;
    }
}