[프로그래머스]이분탐색-입국심사

• 첫번째 풀이

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        ArrayList<Long> snipet = new ArrayList<>();
        long[] select = new long[times.length];
        for(int i=0; i<times.length; i++){
            select[i] = times[i];
        }

        while(snipet.size()!=n){
            long min = select[0];
            for(int i=0; i<select.length; i++){
                if(min > select[i]) min = select[i];
            }
            snipet.add(min);
            ArrayList<Integer> minIndex = new ArrayList<>();
            for(int i=0; i<select.length; i++){
                if(select[i]==min){
                    minIndex.add(i);
                }
            }
            minIndex.sort(null);
            select[minIndex.get(0)] += times[minIndex.get(0)];
            minIndex.clear();
        }
        snipet.sort(null);

        // for(int i=0; i<snipet.size(); i++){
        //     System.out.println(snipet.get(i));
        // }

        return snipet.get(n-1);
    }
}

알고리즘은 맞는 것 같은데 시간초과가 났다. 결국 쓸모 없어진 풀이..

• 두번째 풀이

import java.math.BigInteger;

class Solution {
    public long solution(int n, int[] times) {
        int biggest = times[0];
        for (int i = 1; i < times.length; i++){
            biggest = Math.max(biggest, times[i]);
        }

        long l = 0;
        long r = (long)biggest * (long)n;

        while (l < r){
            long mid = (r-l)/2+l;
            long numP = numProcessed(mid, times);
            if(numP >= n){
                r = mid;
            } else{
                l = mid+1;
            }
        }

        return l;
    }

    long numProcessed(long mid, int[] times)
    {
        long numP = 0;
        for (int i=0; i<times.length; i++){
            numP += mid / times[i];
        }
        return numP;
    }
}

다른 사람의 풀이를 참고하여 작성.

이진탐색을 이용해 답을 구하는건데 답은 times의 모든 element로 나눴을 때 그 몫들의 합이 n이 되는 시간을 찾는 거였다..(그러면 그 시간 내에 그 사람 수만큼 검사하고 끝나는 것이므로)

역발상이 중요한 것이었다..! 다른 것을 이용해 시간을 구해나가는 것이 아니라 시간들의 후보에서 사람 수에 맞는 시간을 찾아나가는 것.. 가끔 이런 문제들이 있어서 접근 방법을 익혀놓아야겠다.