[프로그래머스] 입국심사(Java, Level.3)

문제

입국심사를 기다리는 사람 수 n명

각 심사관이 한명을 심사하는데 걸리는 시간이 담긴 배열 times

 

모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수 구현 

 

입출력의 예

 

풀이

 

너무 어렵당....!

 

이분탐색에 대한 공부도 필요했다! 

 

이분 탐색을 통해서 최소 시간과 최대 시간의 중간 시간 동안 얼마나 많은 인원 심사 완료할 수 있을지 비교해여야 한다. 

만약 완료되었을 경우 최소 시간을 구하기 위해 이분탐색을 사용하여 구한다. 

그렇지 않을 경우에는 더 큰 시간과 비교한다.

 

이분탐색을 통해서 전체 크기에서 절반의 크기만 살펴보기에 1부터 시작하기는 것보다 더 빨리 찾을 수 있다. 

 

1. 이분탐색

이분탐색이란 내림차순 혹은 오름차순으로 정렬되어 있는 수열에서 원하는 값을 검색하는 알고리즘이다. 

 

[ 윈리 ]

1. 배열을 오름차순으로 정렬 

2. 중간 값 추출 

  >> 중간값 = (min + max) / 2

3. 구할 값 == 중간 값

  >> 값 반환 후 종료 

  >> 만약 그렇지 않으면 4번으로 

 

4. 비교 위치 구하기 

  if(구할 값 > 중간 값) 

    >> 중간 +1 ~ max 구간 확인 

  else

    >> min ~ 중간 -1 

5. 2번부터 계속 반복 

 

[이분탐색 참고]

https://charles098.tistory.com/133

[ 알고리즘 ] 이분탐색(Binary Search), upper_bound, lower_bound (C++)

 

 

2. 코드 풀이   

 

2-1. 변수 설정 

answer : 반환 값 

오름차순 정렬 

start : 최소시간 즉, times의 첫번째 원소

end : 최대시간 즉, times의 마지막 원소 * n 

>> 가장 오래걸리는 시간 * 인원 수 

 

 

2-2. 최소시간 구하기 

 

while문 조건(start가 end보다 커질때까지 반복)을 통해서 최소 시간을 구함  

 

1) 변수 설정 

min : 중간 시간

>> 이분탐색 알고리즘 활용을 위한 중간 값을 의미함

person : min 시간동안 심사완료한 인원 

 

 

2) person 구하기 

n = 6, times = {7, 10} 이라고 가정하자 

min은 (7+60)/2로 33이다.

33분 동안 7분 소요하는 심사관은 33/7 = 4명을 

10분 소요하는 심사관은 33/10 = 3명을 완료한다. 

총 7명 완료한다. 

 

해당 부분을 for문을 사용하여 구현하였다. 

 

 

3) 최소시간 찾기 

person >= n 조건이다. 

person이 크거나 같을 경우에는 앞부분 비교하여 기존의 min보다 작은 수을 찾아야 한다. 

반대의 경우 뒷부분 비교하여 기존의 min보다 큰 수를 찾아야 한다. 

각 상황에 대해 설명하겠다. 

 

1. 앞부분 비교

  >> 작은 수 찾기 

answer에 기존의 min의 값을 저장한다. 

  >> min의 최소값을 구하기 위해 앞부분 비교 시, 해당 값을 저장한다. 

end의 값을 min-1를 저장함으로써 다음차례에 start ~ min-1 구간에서 min의 값을 찾을 수 있도록 한다. 

 

2. 뒷부분 비교 

  >> 큰 수 찾기 

start의 값을 min+1를 저장함으로써 다음차례에 min-1 ~ end 구간에서 min의 값을 찾을 수 있도록 한다. 

 

 

4) 변수의 값 보기 

엑셀을 통해서 while문에 구현되어 있어 있는 코드로 인해 변하는 값을 살펴보았다. 

4번째에서 persom이 6으로 n과 값이 동일하지만 종료되지 않았다. 

while문 조건(start가 end보다 커질때까지 반복)에 의해서 계속 진행하여 6번째에서 최소 시간을 구할 수 있었다. 

 

 

 

 

최종 코드

import java.util.*;

 

public long s6(int n, int[] times) {

        System.out.println("입국심사");

        // 1. 변수 설정

        long answer = 0;

        long start = (long) times[0]; // 최소 시간

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

        // 2. 최소시간 구하기

        while (start <= end) {

            // 2-1. 중간 시간 구하기

            long min = (start + end) / 2; // 중간 시간

            long person = 0; // min 동안 입국심사 완료한 사람

            // 2-2. min 동안 입국심사 완료한 인원 구하기

            for (int i : times) {

                person += min / i;

            }

            // 2-3. 비교 부분 찾기

            // 심사완료 인원 <= 심사해야할 인원

            if (person >= n) {

                // 1) 앞쪽(작은쪽) 부분 비교

                /*

                 * 모든 인원을 완료함..

                 * >> min보다 더 적은 시간을 사용해야할 경우가 있는지 확인

                 * >> start ~ min - 1 부분 확인 필요

                 *

                 * < 해당 부분에서 min을 저장하는 이유 >

                 * person == n 과 같은 상황일 때 최소 시간을 구하여야 함.

                 * 따라서 작은쪽과 비교할 경우에 min의 값을 저장하여 최소 시간 구함

                 */

                answer = min;

                end = answer - 1;

            } else {

                // 2) 뒤쪽(큰쪽) 부분 비교

                /*

                 * 모든 인원을 완료하지 못함..

                 * >> min보다 더 많은 시간을 사용해야 함

                 * >> min + 1 ~ end 부분 확인 필요

                 */

                start = min + 1;

            }

        }

        return answer;

    }

 

 

프로그래머스 문제

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

프로그래머스