99클럽 코테 스터디 3일차 TIL - 입국심사 : 프로그래머스 - 이분탐색

1. 오늘의 문제 - 입국심사

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

프로그래머스

 

입국심사를 받을 사람 n명이 주어지고, 각 입국 심사관의 심사 시간이 배열로 주어진다.

가령, n = 6, times = [7, 10] 으로 주어진다면

입국심사를 받을 사람은 6명이고, 입국 심사관은 2명이고, 각각 7분, 10분이 걸린다는 의미다.

자세한 제한사항은 링크를 통해서 확인하도록 하고...

 

2. 문제풀이 전략

2 - 1. times 배열 정렬

입국 심사관의 심사 시간 배열은 정렬되어 주어지지 않는다. 

일단 정렬한다.

java.utils.Arrays.sort(times);

 

2 - 2. 이분탐색

주어진 입력을 가지고 생각해보자.

6명이 심사를 받을 건데, 입국 심사관은 2명이고 각각 7분, 10분이 걸린다면,

가장 오래 걸릴 때는 총 몇 분이 걸릴까?

가장 느린 입국 심사관이 6명을 모두 심사하면 가장 늦지 않을까?ㅋㅋ

10분 * 6명 = 60분이다.

아하! 가장 오래 걸릴 때는 60분이 걸리겠구나!

 

그렇다면, 가장 빨리 6명이 입국 심사를 받는 경우는 무엇일까?

가장 빠른 입국 심사관이 6명을 모두 심사할 때?

이건 아니다.

오래 걸리는 심사관이 도와주면 더 빠를 것이다.

가장 빠른 심사관이 6명을 다 하면,  

7 * 6 = 42분이다.

 

문제에서 주어진 정답은 28분.

28분은 어떻게 구해진 걸까?

0분 부터 가장 오래 걸리는 60분까지 1분씩 늘려가며 입국 심사가 모두 가능한지를 따져보는 것이다.

 

근데, 이렇게 완전탐색으로 찾으면 비효율적이니 이분탐색으로 찾는 것이다.

30분일 때, 입국심사가 가능한가? OK

15분일 때, 입국심사가 가능한가? NO

23분일 때, 가능한가? OK

26분일 때, OK

28분일 때, OK

29분일 때, NO

 

28분에서 가능이고, 29분에서 불가능이네?

아! 그러면 28분이 최선이구나

 

3. 풀이

package io.conduktor.demos.dfsbfs.hanghaecote99.middler;

import java.util.Arrays;

// 3. 프로그래머스 : 입국심사 - 이분탐색
public class Immigration3 {

    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);
        long left = 0;
        long right = times[times.length-1] * (long)n;
        int interviewer = times.length;

        while(left <= right) {
            long mid = (left + right) / 2;
            long complete = 0;
            for (int i = 0; i < interviewer; i++) {
                complete += mid / times[i];
            }
            if (complete < n) {
                left = mid + 1;
            } else {
                right = mid - 1;
                answer = mid;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Immigration3 T = new Immigration3();
        System.out.println(T.solution(6, new int[] {7, 10}));
    }
}

 

4. 소감

이분탐색 3일째 풀고 있는데, 뭔가 익숙해지지는 않는 것 같다.

뭔가 불편하고, 바로바로 어떻게 풀어야할 지 떠오르지 않는 느낌?

너가 이기나 내가 이기나 해보자.