[이분탐색] 입국심사 - JAVA

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

프로그래머스

---

예전에 한 두번 정도 풀었던 문젠데, 내가 워낙 이분 탐색에 약하기도 하고 로직이 기억도 안나서 그냥 다시 품!

 

솔직히 보자마자 기억이 안나서 10분 정도 고민하다가 블로그 찾아봤는데

이해가 너무 잘되어서 잠이 깰 정도였다!!!!!

그 블로그는 아래에 써두었다 ^^

 

이제 풀이 과정을 설명해보겠다

 

 

풀이 과정

우선 우리가 이분 탐색으로 찾아야 할 target은 사람 수 이다!

즉, 시간을 기준으로 이분 탐색하면서 현재 시간으로 목표한 사람 수가 입국심사를 받을 수 있는가?

여기에 초점을 두고 구현한다!

 

우선 제일 빠른 시간(start)와 제일 느린 시간(end)를 정해야 한다

제일 빠른 시간은 입국 심사 시간이 1이고 사람 수도 1명일 때이다

제일 느린 시간은 입국 심사 시간은 times에서 가장 느린 시간이고, 사람 수는 n명일 때이다

 

여기서 주의할 점이 있는데, 테스트 케이스의 n과 times 원소가 너무 커서 int로 하면 범위가 벗어날 수 있다

따라서 long 타입으로 바꿔주는 과정이 필요하다!

 

그 다음 while문을 통해 start가 end보다 작거나 같은 동안에만 반복하며 시간(mid)를 구한다

이분 탐색인 만큼 mid는 start와 end의 중간 값이다

 

그리고 for문을 통해 현재 시간인 mid에서 각각 입국 심사위원들이 몇 명을 심사할 수 있는지 구해서 더해준다

 

예를 들어 현재 시간이 28분이고 각각 심사는 [7, 10] 씩 걸린다고 해보자

그럼 각각 현재 시간을 입국 심사 시간으로 나누면 각각 4명, 2명의 심사가 가능한 것이다

 

요런 식으로 총 입국 심사한 사람 수 (sum)을 구한다

 

이 sum이 만약 주어진 n보다 크거나 같으면 시간을 더 줄일 수도 있기 때문에 

우선 answer에 현재 시간(mid)을 저장해두고, end를 줄여서 다시 이분 탐색한다

 

만약 sum이 n보다 작으면 시간이 모자른 거니까 start를 늘리고 다시 이분 탐색한다

 

 

💡 주의할 점
- long 처리
- sum이 n과 같아도 더 줄일 수 있다는 거, 단 answer에 현재 mid 저장해두고 다시 돌려보기 (마지막일수도 있으니까)
- times 정렬해야 된다는거
- 최소 시간은 1이고, 최대 시간은 times의 가장 큰 원소 * n명 이라는거

 

 

 

 

자바 코드)

import org.junit.Assert;
import org.junit.Test;
import java.util.Arrays;

public class BS1 {
    public long solution(int n, int[] times) {
        long answer = 0;
        Arrays.sort(times);
        long start = 1;
        long end = (long)times[times.length-1] * n;

        while(start<=end) {
            long mid = (start+end)/2;
            long sum = 0;

            for (int time : times) {
                sum += mid / time;
            }

            if(sum >= n) {
                end = mid - 1;
                answer = mid;
            } else {
                start = mid+1;
            }
        }
        return answer;
    }

    @Test
    public void test() {
        Assert.assertEquals(28, solution(6, new int[] {7, 10}));
    }
}

 

 

---

참고 블로그)

https://geunzrial.tistory.com/39

프로그래머스 3단계 입국심사[java]

여기 설명 보면서 차근차근 했더니 잠 깨면서 이해 됨!

최고야 ><