99클럽 코테 스터디 13일차 TIL [이분탐색]

- 오늘의 학습 키워드 : 이분탐색

[문제 이름 : 입국심사  (프로그래머스, Lv 3) ]

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

 

내가 작성한 코드는 아래와 같다.

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
        long answer = 0;
        long start = 0;
        // 모든 사람이 제일 오래 걸리는 심사대로 입국을 받을 때 걸리는 시간
        long end = (long) times[times.length - 1] * n;

        while(start <= end) {
            long mid = (start + end) / 2;
            long count = 0;
            for(int i=0; i< times.length; i++) {
                // 각 심사관마다 mid의 시간일 때 최소 몇 명을 검사할 수 있는지를 계산
                count += mid / times[i];
            }
            if (count < n) {
                // 모든 사람이 검사를 받을 수 없으므로, 더 높은 시간대에서 탐색
                start = mid + 1;
            } else {
                // 모두 검사를 받았지만, 최솟값이 존재할 수 있으므로 값 갱신
                answer = mid;
                end = mid - 1;
            }
        }
        return answer;
    }
}

[풀이 과정]

문제 시작 전 '이분 탐색'이라는 키워드가 없었다면, 쉽게 떠올리지 못했을 것 같다.

이분 탐색 유형의 문제를 풀다 보면 감이 잡히긴 하는데, 아직 바로 떠올릴 정도의 수준까지 올라오진 못한 것 같다.

비슷한 유형의 문제들을 조금만 풀어봤어도 쉽게 풀 수 있는 문제였다.

 

1. 이분 탐색을 하기 위해, times 배열을 오름차순으로 정렬한다.

2. 이분 탐색을 위해 start, end값을 지정해줘야 하는데, 각 인원이 제일 오래 걸리는 심사관을 거쳤을 때를 end값으로 지정해두면, 이 값이 소요되는 시간의 최댓값이 된다. 따라서 start, end 값을 위 코드와 같이 저장하고, 이분 탐색을 시작한다.

3. 이분 탐색은 중간값을 찾고, 특정 조건에 따라 중간값의 왼쪽에서 탐색을 계속할지, 또는 중간값의 오른쪽에서 탐색을 계속할지를 분류한다. 

4. 이때, 각각의 심사관으로만 심사를 받았을 때 걸리는 시간(count)를 계산해보자. 입력문의 예시대로 n = 6, times = {7,10} 이라고 했을 때, start = 0이고, end = 10 * 6 = 60이다.

5. 반복문을 돌렸을 때 mid = (0 + 60) / 2 = 30이고, 30분일 때 각 심사관에게만 모든 사람이 검사를 받는다고 가정해보자. 위 예시의 경우, 0번 심사관은 7분, 1번 심사관은 10분이 소요되므로 count = (30 / 7 ) + (30 / 10 ) = 7이 된다.

6. count < n인 경우, n만큼의 사람에 대해 모두 검사를 할 수 없는 경우이므로, start = mid+1로 갱신하여 오른쪽에서 다시 검색을 시도한다.

7. count <= n인 경우, 시간의 최소값을 구해야 하므로, while문을 반복하면서 최소 값을 갱신한다.

 

 

풀이 시간 : 20분

 

내일은 인프런 강의 Part2. Array 부분을 복습할 예정이다.