[코딩테스트] 프로그래머스 - 입국심사(Java)

🎏 설명

레벨: 3
언어: 자바(Java)

🃏 느낀점

해당 문제는 이분탐색문제입니다.
이분탐색 문제를 풀어본 경우가 있어 어떠한 지점을 포커스를 두고 풀어내야할지 생각을 해봤습니다..

풀이방법
1. 루프돌리기, 한 심사위원만 사용하여 최소시간으로 끝낼수 있는 경우 배열 sorting
2. 최대값으로 한 심사위원만 사용하여 최소시간으로 끝낼수 있는 경우 대입
3. 이분탐색 시도 중간값, 해당시간때 발생할수 있는 사람수 변수 선언
4. 시간때별로 발생할수 있는 사람 경우 변수 대입
5. 최소값, 최대값 범위차이 끝까지 줄이기
6. 이분탐색이 더 불가한경우에 반환

가장 좋아요 많이 받은 코드랑 비교해보겠습니다
차이점은
1. 재귀호출 방식
2. 제가 한 방식은 사람수 더해가기, 좋아요 많이 받은코드는 사람수 빼기(사실 별차이 없습니다 ㅎㅎ)

이로 인한 차이는 좋아요 많이 받은 코드는
메서드 콜스택에 누적되서 공간복잡도가 더 든다고 생각합니다

나머지는 풀이방법 비슷합니다(사실 2분탐색 풀이방법은 비슷비슷합니다)

🎲 내가 작성한 코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        long start = 0,
             end = (long) times[0] * (long) n;
        
        while(start <= end) {
            long mid = (start + end) / 2,
                 humans = 0;
            
            for(int i = 0; i < times.length; i++) humans += mid / times[i];
            
            if(humans >= n) end = mid - 1;
            else start = mid + 1;
        }

        return start;
    }
}

🎯 가장 좋아요 많이 받은 코드

import java.util.Arrays;

class Solution {
    public int solution(int n, int[] times) {
        Arrays.sort(times);
        return (int) find((long) n, times, (long) times.length, times[0], (long) ((long) times[0] * (long) n));
    }

    public long find(long n, int[] times, long nExamination, long from, long to) {
        long minTime;
        long tmp = n;
        if (from == to) {
            return from;
        }
        else {
            minTime = (from + to) / 2;// + ((from + to) % 2 == 1? 1 : 0);
            for (int i = 0; i < nExamination; i++) {
                tmp -=  minTime / (long) times[i];
            }
            if (tmp > 0) {
                return find(n, times, nExamination, minTime + 1, to);
            }
            else {
                return find(n, times, nExamination, from, minTime);
            }
        }
    }
}