[코테연습] 2560. House Robber IV

https://leetcode.com/problems/house-robber-iv/?envType=daily-question&envId=2025-03-15

 

1️⃣ 문제 타입

• 이진 검색 (Binary Search on Answer)
• 그리디 알고리즘 (Greedy)
• DP와 유사한 비연속 부분 수열 문제
• 결정 문제 (Decision Problem) 접근 가능

---

2️⃣ 문제 분석

• nums[] 배열이 주어졌을 때, 비연속적으로 k개의 집을 털 수 있는 최소 capability를 구하는 문제.
• **capability(최대값 제한)**을 조절하면서 k개의 집을 선택해야 함.
• 비연속적인 집만 털 수 있음 → 연속된 집을 선택하면 안 됨.
• 목표는 가장 작은 capability를 찾는 것.

💡 이진 검색(BS)로 답을 찾을 수 있는 이유?

• capability가 작을수록 k개의 집을 털기 어려워짐.
• capability가 크면 쉽게 털 수 있음.
• 즉, capability의 최솟값을 찾기 위해 이진 검색을 활용 가능!

---

3️⃣ 문제 풀이

✅ Step 1: 이진 검색 범위 설정

• 가능한 capability 값의 최소, 최대를 찾음.
  • left = min(nums), right = max(nums) 로 설정.

✅ Step 2: mid 값으로 k개의 집을 털 수 있는지 확인 (isPossible 함수)

• 배열을 탐색하면서 mid 이하의 값만 선택 가능.
• 연속적으로 선택하면 안 되므로, 턴 집 다음 집을 건너뛰어야 함 (i += 2).
• count >= k이면 true, 아니면 false.

✅ Step 3: 이진 검색 진행

• isPossible()이 true라면 더 작은 capability도 가능한지 확인 → right = mid
• false라면 더 큰 capability가 필요 → left = mid + 1
• 결과적으로 left가 최소 capability가 됨.

⏳ 시간 복잡도: O(N log M)

• O(log M): 이진 검색 (M = max(nums) - min(nums))
• O(N): isPossible() 함수 실행

 

 

> java

 

import java.util.Arrays;

class Solution {
    // \U0001f3e0 k개의 집을 털 수 있는지 확인하는 함수
    private boolean canStealKHouses(int[] nums, int k, int capability) {
        int count = 0; // 털 수 있는 집의 개수
        int i = 0; // 배열 인덱스
        
        while (i < nums.length) {
            if (nums[i] <= capability) { // 현재 집의 돈이 capability 이하이면 털 수 있음
                count++;
                i += 2; // 비연속적인 집을 털어야 하므로 한 칸 건너뛰기
            } else {
                i++; // 현재 집을 못 털면 다음 집으로 이동
            }
        }
        
        return count >= k; // 최소 k개의 집을 털 수 있는지 확인
    }

    public int minCapability(int[] nums, int k) {
        // \U0001f3e0 가능한 최소 및 최대값 설정 (이진 검색 범위)
        int left = Arrays.stream(nums).min().getAsInt(); // 배열에서 최솟값 찾기
        int right = Arrays.stream(nums).max().getAsInt(); // 배열에서 최댓값 찾기

        // \U0001f3af 이진 검색 수행 (최소 최댓값 찾기)
        while (left < right) {
            int mid = left + (right - left) / 2; // 중간값 계산 (오버플로우 방지)

            if (canStealKHouses(nums, k, mid)) {
                right = mid; // 더 작은 capability로도 가능할지 확인 (최솟값을 찾기 위해)
            } else {
                left = mid + 1; // mid 값이 너무 작아 k개의 집을 털 수 없는 경우, 범위를 증가
            }
        }

        return left; // 최소 capability 반환
    }
}

 

 

>python 

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        left = min(nums)
        right = max(nums)
        while left < right :
            mid = int (left + (right - left) / 2)
            if self.isPossible(nums, k, mid) :
                right = mid
            else :
                left = mid + 1

        return left

    def isPossible(self, nums : List[int], k : int, mid : int) :
        cnt = 0
        idx = 0
        while idx < len(nums) :
            if nums[idx] <= mid :
                cnt+=1
                idx+=2
            else :
                idx+=1
            
        return cnt >= k