[43238] 입국심사

✔ 입국심사

[프로그래머스 43238]

문제 분석하기

전체 인원 입국에 걸리는 시간의 최소와 최대를 이진 탐색의 인덱스로 설정한 후

이진 탐색을 하며 시간 안에 모든 인원을 처리할 수 있는지 계산

걸리는 시간을 계속해서 이진 탐색하면서 최소 시간을 구함

손으로 풀어보기

1. 이진탐색을 위해 데이터 정렬
2. 걸리는 시간의 최소와 최대를 찾기
   • 최소 : 0은 시작 인덱스
   • 최대 : 가장 길게 걸리는 심사관의 시간 * n명은 종료 인덱스
3. 이진 탐색
   • 시작 인덱스 > 종료 인덱스일 때까지 수행
   • 중앙값 크기로 모든 입국이 가능하다면 종료 인덱스 = 중앙값 - 1
   • 중앙값 크기로 모든 입국이 불가능하다면 시작 인덱스 = 중앙값 + 1
4. 최소 시간 반환

슈도코드 작성하기

n(입국 인원수)
times(심사관마다 걸리는 시간)
answer(모든 사람이 심사를 받는데 걸리는 시간의 최솟값)
times 정렬
start(이진 탐색 시작 인덱스) = 0
end(이진 탐색 종료 인덱스) = 가장 길게 걸리는 심사관의 시간 * n명
이진 탐색 수행
while(시작 인덱스 <= 종료 인덱스) {
    mid(중간 인덱스)
    count(입국 가능한 인원수)
    for(심사관마다 걸리는 시간) {
        count += mid / times[i]
    }
    if(중간 인덱스 값으로 모든 인원 입국 불가능) {
        시작 인덱스 = 중앙 인덱스 + 1
    }
    else(중간 인덱스 값으로 모든 인원 입국 가능) {
        종료 인덱스 = 중앙 인덱스 - 1
        answer = mid 갱신
    }
}
answer 반환

코드 구현하기

/**
 * 43238) 입국심사
 */
public class K001_43238 {
    // n(입국 인원수)
    // times(심사관마다 걸리는 시간)
    public long solution(int n, int[] times) {
        // 범위가 100000000이므로 int형 대신 long형 사용
        // answer(모든 사람이 심사를 받는데 걸리는 시간의 최솟값)
        long answer = 0;
        // times 정렬
        Arrays.sort(times);
        // start(이진 탐색 시작 인덱스) = 0
        long start = 0;
        // end(이진 탐색 종료 인덱스) = 가장 길게 걸리는 심사관의 시간 * n명
        long end = (long) times[times.length - 1] * n;
        // 이진 탐색 수행
        while (start <= end) {
            // mid(중간 인덱스)
            long mid = (start + end) / 2;
            // count(입국 가능한 인원수)
            long count = 0;
            // 심사관마다 입국 처리
            for (int i = 0; i < times.length; i++) {
                count += mid / times[i];
            }
            // 중간 인덱스 값으로 모든 인원 입국 불가능하다면
            if (count < n) {
                // 시작 인덱스 = 중앙 인덱스 + 1 (시간 추가)
                start = mid + 1;
            }
            // 중간 인덱스 값으로 모든 인원 입국 가능하다면
            else {
                // 종료 인덱스 = 중앙 인덱스 - 1 (시간 감소)
                end = mid - 1;
                // answer = mid 갱신
                answer = mid;
            }
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K001_43238 solution = new K001_43238();

        int n = 6;
        int[] times = { 7, 10 };

        long result = solution.solution(n, times);

        System.out.println(result);
    }
}