99클럽 코테 스터디 22일차 TIL + 이분탐색(입국심사)

오늘의 과제

프로그래머스 Lv.2 이분탐색으로 분류된 입국심사입니다.

 

이번 유형은 Binary Search(이분탐색) 입니다.

문제

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

프로그래머스

 

 

먼저 문제 요구사항 요약입니다.

 

입국 심사를 받을 n명이 있고 심사시에 time 만큼 걸리는 심사관이 times 만큼 주어집니다.

 

이 때, 모든 사람이 심사를 받는 최소값을 반환하면 됩니다.

 

문제의 분류를 보면 아시겠지만 이분 탐색을 이용하여 문제를 풀어나가야 합니다.

 

이분 탐색이란 간단히 설명하면 어렸을 적 많이 하던 top & down 게임을 생각하면 편합니다.

 

다음과 같은 숫자 범위 중 여러분은 6을 찾아야 합니다.

 

만약 처음에 정석대로 중간 값인 5를 외치고 출제자가 Up을 외친다면

범위는 다음과 같아지겠죠?

 

 

이런식으로 중간값을 기준으로 답보다 큰 수인지, 작은 수 인지 범위를 좁혀가며

문제의 답을 찾아가면 됩니다.

 

그럼 최소값은 0으로 잡으면 된다고 치고, 최고값은 어떻게 설정해야 할까요?

 

문제에서 주어진 최악의 값을 생각하면 최고값을 설정할 수 있습니다.

 

입국 심사가 각 time 만큼 걸리는 심사관이 times 만큼 있다고 했으니

가장 오래 걸리는 심사관한테 모두 받는 경우가 가장 최악의 경우의 수가 되겠죠?

 

따라서 times가 정렬되어 있다는 가정하에 times[times.length - 1] * n이 최고값이 됩니다.

 

이제 위에 값들 중 왼쪽 값을 lt, 오른쪽 값을 rt, 중간 값을 mid라 칭하고 정리해보겠습니다.

 

lt ~ rt 사이의 값인 mid는 변수명 그대로 중간값이니 (lt + rt) / 2로 설정하고,

해당 중간값 안에 n만큼의 사람을 처리할 수 있는지 없는지를 판별하며 범위를 좁혀 나가면 됩니다.

 

문제의 예시인 n = 6, times = [7, 10]으로 살펴보겠습니다.

 

기본값으로 lt는 0에서 출발하면 되고, rt는 마지막 값에서 n을 곱한다고 했으니 60이 됩니다. (n * 10 = 60)

 

그럼 mid는 (lt + rt) / 2에 의해 (0 + 60) / 2가 되니 30에서 출발하는데

7분 걸리는 심사관에 의해 4명, 10분 걸리는 심사관에 의해 3명 총 합 7명을 처리할 수 있으니

n을 충족합니다.

 

다만, 아직 7명을 처리하는 시간인 30분이 최적의 값인지는 판별하지 않았으니 찾기 위해

n을 초과했으니 rt의 값을 줄입니다.

 

이 때, rt의 값은 mid - 1의 값으로 설정합니다.

 

그럼 다시 위의 로직을 lt = 0, rt = 29, mid = 14에서 탐색합니다.

 

14는 7분 걸리는 심사관은 2명, 10분 걸리는 심사관은 1명으로 n보다 미달되어

답이 될 수 없습니다.

 

그렇다면 초과 했을 때랑은 반대로 lt의 값을 mid + 1로 설정하여 다시 탐색을 해나가야겠죠?

 

위 방법대로 mid가 최적의 값이 될 때 까지 탐색을 이어나가면 됩니다.

 

 

코드입니다.

class Solution {
    public long solution(int n, int[] times) {
        long answer = Long.MAX_VALUE;
        
        long lt = 0;
        long rt = (long) times[times.length - 1] * n;
        
        while(lt <= rt) {
            long mid = (lt + rt) / 2;
            long cnt = 0;
            for(int time : times) {
                cnt += mid / time;
            }
            if(cnt >= n) {
                answer = Math.min(answer, mid);
                rt = mid - 1;
            } else {
                lt = mid + 1;
            }
        }
        
        return answer;
    }
}

 

 

배운 점

DP가 아닌 할 줄 아는 이분탐색이 나와 조금 신났습니다.

 

많은 문제까지는 아니어도 기본적으로 lt, rt, mid를 활용하여 푼다는 점을 기억하고 있으니

문제의 요구사항만 제대로 읽어도 쉽게 풀 수 있는 문제였습니다.

 

그러면 안되는데 이전에 작성한 글을 읽어보니 작성자가 잘 이해하면 이해할수록

조금 더 상세하고 쉬운 설명이 가능해지는 것 같습니다.

 

코테 공부가 아닌 일상적인 회고나 글을 쓸 때에도 양질의 기록을 위해

조금 더 이해하고 작성하는 연습이 필요할 것 같습니다.

 

 

오늘의 한줄평

진정한 고수는 어린 아이나 노인에게도 가르칠 수 있어야 한다.