[Leetcode 10/100] Find the Smallest Divisor Given a Threshold - Medium

leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/

Find the Smallest Divisor Given a Threshold - LeetCode

문제 풀이 방식

이진 탐색을 활용한 구현

주의할 점

문제를 정확하게 이해하는 것이 가장 중요하다고 느꼈다. -> 문제를 한번에 이해하지 못해서 많은 시간이 소모 됨.

완전 탐색으로 시도할 경우 시간복잡도가 10^6 * 10^4 => 10^10 까지 나올 수 있어 TLE를 만날 수 있게 된다.

그러므로 이진 탐색을 이용하여 시간 복잡도를 줄이는 코드를 작성할 필요가 있다.

그럴 경우 Log(10^6) * 10^4가 최대이므로 TLE를 피할 수 있게 된다.

또한 코드에서 중간 값을 단순하게 left + right / 2로 나누게 될 경우 overflow가 발생하게 된다.

그러므로 번거롭겠지만 left + (right - left) / 2로 작성해줘야 한다. (python은 상관 없다. 코딩테스트 언어를 python으로 바꾸려고 고민중이다.. 이 이유때문은 아니지만 ㅎㅎ)

소스코드

class Solution {
        int res;
        public int smallestDivisor(int[] nums, int threshold) {

            int left = 1;
            int right = 1000000;

            while(left < right){
                int mid = left+(right-left)/2;
                res = findSmallDivisor(nums, mid);
                if(res > threshold){
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            return left;
        }

        private int findSmallDivisor(int[] nums, int left) {

            int sum = 0;

            for(int i=0; i<nums.length; i++){
                if(nums[i]%left == 0){
                    sum += nums[i]/left;
                } else {
                    sum += nums[i]/left + 1;
                }
            }

            return sum;

        }

    }

 

Binary Search를 활용하는 풀이를 학습하기에 좋은 글이 있어 공유합니다. 참고하세요!

leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/discuss/777019/Python-Clear-explanation-Powerful-Ultimate-Binary-Search-Template.-Solved-many-problems.