[프로그래머스] 입국심사 for Java

 

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

프로그래머스

 

 

 

 

---

 

입국심사를 n명이 하는데에 걸리는 최소 시간을 구하는 문제이다.

 

 

근데 이제 대기자가 1,000,000,000명을 곁들인...

 

10억..명....?

 

 

그리고 각 심사관이 한 명을 심사하는데 걸리는 시간도 1분 이상 1,000,000,000분 이하이다.

 

이렇게 큰 수가 나오면 의심해볼 것 : 이분탐색

 

 

그래서 이분탐색으로 방향을 잡았다.

 

 

이분탐색이라 하믄.... left, mid, right를 정하고 반씩 나눠가면서 탐색을 할 것이다.

 

그렇다면 무엇을 기준으로 할 것인지 정해야함

 

여기에 후보가 2가지가 있다.

 

1. 심사 기다리는 사람 수

2. 걸리는 시간

 

그런데 return돼야하는 값도 걸리는 시간이니까 후자겠지...라고 생각했다.

 

그럼 right 값으로 놔야하는 최대 걸리는 시간은?

 

심사하는데 걸리는 시간 중 최소값 x 인간 수!

 

그러니까 그냥 빨리 입국심사 찍어주는 사람에게 모든 사람이 간다고 하면 저 값이니까 저걸로 잡았다.

 

 

코드

 

import java.util.*;
class Solution {
    public long solution(int n, int[] times) {
        long answer = 1000000000;
        long left = 0, right = 1000000000, mid = 0;
        
        if(n <= 2) return 0;
        
        Arrays.sort(times);
        right = (long)n * times[times.length - 1];
        
        while(left <= right){
            long person = 0;
            mid = (left + right) / 2; // 걸리는 시간
            System.out.println(left + " " + mid + " " + right);
            
            for(int i=0; i<times.length; i++){ // 한 심사대에서 그 시간 안에 받을 수 있는 사람 수 더함
                person += mid / times[i];
            }
            System.out.println(person);
            
            if(person >= n){ // 심사대에서 받을 수 있는 사람 수가 많으면 시간을 줄여야지
                right = mid-1;
                answer = mid;
                
            } else{
                left = mid+1;
            }
            
        }
        return answer;
    }
}

 

처음 answer 값을 저걸로 잡을 필요는 전혀전혀 없다.

 

처음에 answer = Math.min(min, answer)로 잡았어서 저렇게 넣었는데 어차피 탐색을 다 돌꺼기 때문에 마지막 값이 최소값이 될 수밖에 없음

 

 

그리고 주의할점!!!!

 

right = (long)n * times[times.length - 1];

 

이거!!!!! int인 n을 long타입으로 캐스팅해주고 계산해야 제대로 된 right 값이 나온다!

 

long = int * int로 계산하면 int값 두 개가 계산된 후 long타입으로 넣어주는거기 때문에 int값이 넘어가면 overflow가 일어나서 -값으로 바뀐다.

 

이거 때문에 몇번 틀렸다 흑흑...

 

 

그래서 테스트케이스 3,5,7,8 틀리는 사람들은 이 부분을 참고하시길.........

 

 

 

성능