이분탐색 - 입국심사

프로그래머스(이분탐색) - 입국심사

해당 문제는 이분탐색을 이용해 풀면 되는 문제입니다. 문제를 처음 봤을때 생각했던 방식은 우선순위를 통한 풀이입니다. 우선순위의 기준은 각 time + finishTime 으로 했었고, 반복할때마다 큐에서 꺼내고 finishTime 을 업데이트 하여 다시 넣어주는 방식을 생각했습니다. 시간초과가 날 것으로 예상되었지만, 시도해 보았고, 결과 역시 예상대로 시간초과가 되었습니다.

public long solution1(int n, int[] times) {
        long answer = 0;
        PriorityQueue<ImmigrationInformation> priorityQueue = new PriorityQueue<>((o1, o2) -> o1.finishTime + o1.time > o2.finishTime + o2.time ? 1 : -1);

        for(int time : times) {
            priorityQueue.add(new ImmigrationInformation(time, 0));
        }

        for (int i = 0; i < n; i++) {
            ImmigrationInformation information = priorityQueue.poll();
            answer = information.time + information.finishTime;
            information.finishTime = answer;
            priorityQueue.add(information);
        }

        return answer;
    }

    class ImmigrationInformation {
        long time;
        long finishTime;
        ImmigrationInformation(long time, long finishTime) {
            this.time = time;
            this.finishTime = finishTime;
        }
    }

이분탐색 알고리즘 문제라는 힌트를 몰랐다면, 생각하기 쉽지 않았을것으로 생각됩니다. 이 후 풀이는 다른 분들의 풀이와 유사하게 풀었습니다.

public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);

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

        while (minTime <= maxTime) {
            long midTime = (minTime + maxTime) / 2;
            long people = 0;
            for (int time : times) {
                people += midTime / time;
                if (people >= n) {
                    break;
                }
            }
            if (people >= n) {
                answer = midTime;
                maxTime = midTime - 1;
            } else {
                minTime = midTime + 1;
            }
        }

        return answer;
    }