지니로그

오늘의 학습 키워드

이진탐색

알고리즘 문제

• 프로그래머스 Level 2. 입국심사
• https://school.programmers.co.kr/learn/courses/30/lessons/43238

공부한 내용

이진 탐색 (이분 탐색)

• 정렬된 데이터 범위에서 탐색 범위를 반(1/2)만큼 좁혀나가면서 원하는 값을 찾는 알고리즘이다.
• 데이터를 미리 정렬시킨 후 탐색을 해야 한다.
• 시간복잡도: O(logN)

오늘의 회고

처음 시도

• 사실 이진 탐색 알고리즘에 대해 잘 몰라서 찾아보면서 해결해야 했다.
• 처음에 완탐으로 시간을 +1 하면서 검사된 사람 카운트를 해서 n이 되면 반환하는 식으로 풀려다가 조건에 n의 범위가 1 ~ 1000000000이었기 때문에 
  • 먼저 오름차순으로 times 배열을 정렬했다고 가정한다. (times 배열: 각 심사관이 검사하는데 걸리는 시간)
  • n이 1이라면, 심사하는 데 걸리는 시간은 times[0] (최소시간) * 1이 된다.
  • n이 1000000000이라면, 심사하는 데 걸리는 시간은 최악(심사관이 1명)인 경우 times[0] * 1000000000이다. => 백억
• 완탐 시간 복잡도 O(N)
  • 시간복잡도를 볼 때,  보통 1초에 1억(10^8)번 연산 가능하다고 본다.
  • 앞서 완탐으로 생각해본 시간복잡도는 심사관 수 * times[0](최소 검사시간) * n(심사할 사람 수)이다.
  • 심사관이 1명이고 검사시간이 1일 때, 1초에 1억(10^8)번 연산 가능 기준으로 보면 10초 정도 걸릴 것으로 예상된다. 하지만 이것은 최소 기준!
  • 심사관 수는 1~100000 범위인데 심사관과 심사시간이 늘어날수록 연산에 필요한 시간은 엄청나게 늘어나게 된다. => 불가능

해결

• 이진 탐색 시간 복잡도 O(logN)
  • 탐색 범위가 한 번 탐색할 때마다 절반으로 줄어들게 된다.
  • 이 문제가 요구하는 것은 모든 사람(n)이 심사를 받는데 걸리는 최소 시간이다.
  • 이 문제에서 탐색 범위는 가장 빠른 심사관의 심사시간 ~ 가장 빠른 심사관이 모든 사람(n)에 대한 심사시간
    • 최소 범위: 가장 빠른 심사관이 1명을 심사하는 데 걸리는 시간 => times[0]
    • 최대 범위: 가장 빠른 심사관이 모든 사람을 심사하는 데 걸리는 시간 => times[0] * n
  • log2​(최대 탐색 범위)=log2​(최대범위−최소범위)로 최대 이진 탐색 수는 log2 (times[0]*n-times[0])이고, times[0]은 작은 수이기 때문에 log2 (times[0]*n)에 근사하다.
  • 탐색을 반복할 때 중간 값을 계산해서 mid(중간값) 시간 내에 심사할 수 있는 사람 수를 계산 O(1)하는데 심사관 수만큼 반복하므로 시간복잡도가 O(심사관 수)이다. => O(1) + O(M) => O(M)
  • 최종 시간복잡도: O(M log2(times[0]*N))

문제 풀이

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        long answer = 0;
        
        Arrays.sort(times);
        
	long min = times[0];
	long max = times[0] * (long)n;
        while (min <= max) {
            long mid = (min + max) / 2;
            long count = 0L;
            for (int i = 0; i < times.length; i++) {
                count += mid / times[i];
            }
            if (count < n)
                min = mid + 1;
            else {
                max = mid - 1;
                answer = mid;
            }
        }
        
        return answer;
    }
}