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

 

✏️  오늘의 문제 : 1011. Capacity To Ship Packages Within D Days

 

 

📌 주안점

• 저번 문제와 동일하게, 이분 탐색은 크게 두가지 유형이 있다는 것에 주목하자
  • 인덱스로 정렬된 배열에서 특정 값을 찾는 경우
  • 특정 값에 대해서 최적의 값을 찾는 경우
• 이번 문제도 weights는 기준이 되지 못하고, 가장 적은 weight capacity를 찾는 문제이기에 특정 값에 대해 최적의 값을 찾는 이분 탐색을 시행한다.
• weight capacity의 최대값 5*10^4 (weight.length) * 500 (weights[i]) 부터, 0까지의 값을 상대로 이분 탐색을 시행하면서 조건을 만족하는 값을 찾는다.
  • 만족해야 하는 조건 -> 날짜순으로(인덱스 순) weigth capacity를 이용해 weight를 담았을 때,
    • 담은 날짜들이 기준 days를 초과하지 않아야 한다
    • weight[i] < capacity를 만족해야 한다.

 

📌 풀이

class Solution(object):
    def possibleCheck(self, weights, days, cap):
        cnt = 1
        currentSum = 0
        for i in weights:
            if cap < i: return False
            currentSum += i
            if currentSum > cap:
                cnt += 1
                currentSum = i
        return cnt <= days

    def shipWithinDays(self, weights, days):
        """
        :type weights: List[int]
        :type days: int
        :rtype: int
        """
        high = 500*5*(10**4)
        low = 1
        ans = high #한번도 안걸릴 경우 즉, 모든 weights의 값이 high 인 경우
        check = False

        while low+1<high:
            cap = (low+high)//2
            print(low, high, "|", cap)
            check = self.possibleCheck(weights, days, cap)
            if check:
                ans = cap
                high = cap
            else: low = cap
        return ans

 

• 이분 탐색시, weights 배열의 모든 원소가 high값인 경우가 존재할 수도 있어 ans값에 미리 high값을 넣어놓는다.