[프로그래머스] 입국심사

문제

 

 

 

 

분석

해당 문제는 이분법으로 분석이 좀 필요하다.

심사위원은 여러명이고 심사를 최대한 빨리 끝나는 시간을 반환해야 되는 문제이다.

 

1. 최소시간과 최대시간의 범위를 구한다.

2. 최소시간과 최대시간의 중간 시간를 구한다.

3. 중간시간에서 얼마나 처리 할수 있는지 계산한다.

4. 중간시간에 해결이 됐다면 더 작은 범위의 시간으로 계산한다.

5. 중간시간에 해결이 안됐다면 더큰 범위의 시간을 찾는다.

6. 이렇게 최소 시간과 최대 시간의 범위를 줄여 나가면서 최소와 최대가 동일하거나 같은면 종료한다. 

 

 

구현

import java.util.*;

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

        // 최소 시간
        long minTime = 1;

        // 최대 시간
        long maxTime = (long)times[times.length-1] * n;


        // 시작시간 보다 최소시간이 클때만 반복
        while(minTime <= maxTime) {

            // 시간의 중간값 계산 이분탐색
            long midTime = (minTime+maxTime)/2;

            // 검사한 사람의 수
            long examinedPeople = 0;

            // mid 타임 에서 얼마나 검사 할수 있는지 체크
            for (int i = 0; i < times.length; i++) {
                examinedPeople += midTime/times[i];
            }

            // 검사받은 수가 검사받아야할 사람보다 적으면 시간대 증가
            if ( n > examinedPeople ) {
                minTime = midTime +1;

            // 검사받을 수가 검사받아야할 사람보다 작거나 같으면 
            // 더 작은 값에서 검사 수행
            } else {
                maxTime = midTime -1;
                answer = midTime;
            }
        }

        return answer;
    }
}

 

 

 

결과

 

 

 

 

 

 

 

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/43238?language=java 

코딩테스트 연습 - 입국심사