2560. House Robber IV

링크

House Robber IV - LeetCode

문제 설명

• 영문

  There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he refuses to steal from adjacent homes.

  The capability of the robber is the maximum amount of money he steals from one house of all the houses he robbed.

  You are given an integer array nums representing how much money is stashed in each house. More formally, the ith house from the left has nums[i] dollars.

  You are also given an integer k, representing the minimum number of houses the robber will steal from. It is always possible to steal at least k houses.

  Return the minimum capability of the robber out of all the possible ways to steal at least k houses.

이 문제를 해석하면 다음과 같습니다.

집이 연속되게 이어져있고, 그 안에는 돈이 있습니다.

도둑은 이것을 훔치려고 하고, 하지만 그들은 인접한 집의 돈을 훔치길 원하지 않습니다.

또 Capability는 본인이 돈을 훔친 집 중에서, 가장 많은 돈을 훔친 집에서 훔쳐온 돈의 양을 의미합니다.

이후 nums라는 배열이 주어집니다. 이는 각각의 집에 놓여져있는 돈의 양을 의미합니다.

또한, k라는 숫자가 주어집니다. 이는 도둑이 최소한 k개의 집은 털어야 한다는 것입니다.

이러한 조건들이 주어졌을 때, 도둑이 돈을 훔칠 수 있는 모든 경우의 수에서 minimum capability를 구하면 됩니다.

Example 1:

Input: nums = [2,3,5,9], k = 2
Output: 5
Explanation:
There are three ways to rob at least 2 houses:

• Rob the houses at indices 0 and 2. Capability is max(nums[0], nums[2]) = 5.
• Rob the houses at indices 0 and 3. Capability is max(nums[0], nums[3]) = 9.
• Rob the houses at indices 1 and 3. Capability is max(nums[1], nums[3]) = 9.
  Therefore, we return min(5, 9, 9) = 5.

Example 2:

Input: nums = [2,7,9,3,1], k = 2
Output: 2
Explanation: There are 7 ways to rob the houses. The way which leads to minimum capability is to rob the house at index 0 and 4. Return max(nums[0], nums[4]) = 2.

예제는 다음과 같습니다.

접근법

제가 이 문제를 풀기 위해 어떤 식으로 접근했는지 자세히 설명해보겠습니다.

과연 K개를 초과하는 집을 터는 경우의 수를 고려할 필요가 있을까?

Capability는 본인이 턴 집들 중에서 가장 많은 돈을 턴 집에서 가지고 나온 돈의 양을 의미합니다. 즉, 집을 털면 털수록 Capability는 높아질 수 밖에 없습니다.

그렇다는 것은, K개를 초과하는 집을 터는 경우의 수는 고려할 필요 자체가 없는 것 아닐까요?

K개의 집을 터는 모든 경우의 수를 구하면, K개를 초과하는 집을 터는 경우의 수는 이를 포함하고 있는 형태일테니까요.

이로써, K개의 집을 터는 경우의 수만 구하면 되는 것으로 문제를 조금 단순화 시켰습니다.

문제를 바꿔볼 수 있을까?

여기서 더 나아가서, 문제를 아예 바꿔보겠습니다.

저는 이 문제를 보고 가장 어렵다고 느꼈던 부분이 모든 경우의 수를 구해야 한다는 것이었습니다.

근데, 과연 모든 경우의 수를 구할 필요가 있을까요?

짜피 Minimum한 Capability만 구하면 됩니다. 모든 경우의 수를 구하는 것이 아니라, 가장 작은 수로 구성되어 있는 길이 K의 배열을 찾기만 하면 됩니다.

가장 작은 수로 구성되어 있는 길이 K의 배열을 찾아보자

가장 쉽게 할 수 있는 생각은 우선순위 큐에 Nums를 모두 집어넣고, 작은 수부터 순서대로 꺼내가면서, 지금까지 꺼낸 수들로 길이 K의 배열을 만들 수 있는지만 확인하면 됩니다.

만일 길이 K의 배열을 만들기만하면 지금까지 세워온 근거를 통해 이를 답으로 책정할 수 있는 것입니다.

자 그러면 일단, 모든 숫자들을 우선순위 큐에다가 넣어보죠.

struct comp {
	bool operator()(vi & o1, vi & o2) {
	  return o1[0] > o2[0];
	}
};

...

priority_queue < vi, vii, comp > pq;
for (int i = 0; i < n; i++) {
  pq.push({ nums[i], i });
}

자 이제는 우선순위 큐에서 작은 숫자들부터 순서대로 뽑아내면서 길이 K의 배열을 찾기만 하면 됩니다.

이는 어떻게 찾을 수 있을까요?

간단하게 생각하면 됩니다.

어떠한 숫자를 뽑았을 때, 총 4개의 경우가 존재합니다.

• 숫자를 뽑았는데 이미 왼쪽에 인접한 숫자를 뽑은 경우 ex) 1 2 3 이 있고, 2를 뽑았을 때, 1을 이미 뽑은 경우
• 숫자를 뽑았는데 이미 오른쪽에 인접한 숫자를 뽑은 경우 ex) 1 2 3 이 있고, 2를 뽑았을 때, 3을 이미 뽑은 경우
• 숫자를 뽑았는데 이미 양쪽에 인접한 숫자를 뽑은 경우 ex) 1 2 3 이 있고, 2를 뽑았을 때, 1과 3을 이미 뽑은 경우
• 숫자를 뽑았는데 양쪽에 인접한 숫자가 없는 경우 ex) 1 2 3 이 있고, 2를 처음 뽑는 경우

각각의 경우의 수에서 만들 수 있는 배열의 최대 길이는 어떻게 변할까요?

먼저 첫번째 경우의 수부터 분석해보겠습니다.

위에서 예시로 들었던 것에서 조금 더 더해서 1 2 3 4 5라는 배열이 존재한다고 가정해서 예시를 들어보겠습니다.

• 숫자를 뽑았는데 이미 왼쪽에 인접한 숫자를 뽑은 경우

x 2 x x x 이고, 3을 뽑아볼까요?

그러면 x 2 3 x x 가 됩니다.

이렇게 되면 만들 수 있는 배열의 최대 길이는 1 이 됩니다. 2 아니면 3을 선택할 수 있죠. 이전과 길이는 변화가 없습니다.

하지만, 1 2 x x x 인 상태에서 3을 뽑는다고 가정해볼까요?

1 2 x x x 인 상태에서는 최대 길이가 1입니다. 1 아니면 2이죠.

하지만, 여기서 3을 뽑으면 1 2 3 x x 가 되고, 1 3과 같이 2의 배열을 만들 수 있습니다.

뭔가 규칙이 보이지 않나요?

그렇습니다. 인접한 집을 털지 못하는 것이니, 최대 길이를 뽑아내기 위해서는, 연속적으로 이어진 배열의 길이를 2로 나누고 올림해주면 되는 것입니다. 현재의 상황은 길이가 3이니, 2로 나누면 1.5, 올림하면 2인 것입니다.

이를 통해서 수식을 세울 수 있습니다. 다음 경우의 수들을 보면서 이를 확실하게 해보겠습니다.

• 숫자를 뽑았는데 이미 오른쪽에 인접한 숫자를 뽑은 경우

이건 위의 경우의 수에서 반대로 생각해보면 됩니다.

• 숫자를 뽑았는데 이미 양쪽에 인접한 숫자를 뽑은 경우

가장 핵심인 부분입니다.

만일, 1 2 x 4 5 인 상태에서 3을 뽑았다고 가정해보죠.

그럼 1 2 3 4 5 죠? 이전에 선택했었던 숫자들로만은 최대 길이 2의 배열밖에 만들 수 없었는데, 3을 뽑은 순간 1 3 5로 최대 길이 3인 배열을 만들 수 있게 되었습니다.

• 숫자를 뽑았는데 양쪽에 인접한 숫자가 없는 경우

이 경우는, 그냥 x x x x x 인 상태에서 하나의 숫자를 뽑는 것이니까, 무조건 기존보다 + 1 의 길이의 배열을 만들 수 있습니다.

이를 조금 더 포멀하게 정의해보면 다음과 같습니다.

새롭게 숫자를 선택함으로써 새롭게 연속적인 배열이 생기게 됩니다.

이를 통해 현재까지 선택한 수들로 최대 만들 수 있는 배열의 길이를 찾기 위해서는 아래와 같이 수식을 정의할 수 있습니다.

현재 숫자를 선택하기 이전까지 만들 수 있었던 최대 길이 배열의 길이 += 현재 숫자를 선택함으로써 새로 생긴 배열로 만들 수 있는 최대 길이 배열의 길이 - (왼쪽 배열로 만들 수 있는 최대 길이 배열의 길이 + 오른쪽 배열로 만들 수 있는 최대 길이 배열의 길이)

이렇게까지 정의했으면 이제 새롭게 숫자를 선택했을 때 길이 몇의 연속적인 배열이 생기는지 빠르게 계산해주면 됩니다.

그럼 양쪽의 길이가 어떻게 되는지 빨리 알 수 있는 방법이 있나?

저는 이를 빠르게 계산해주기 위해 분리 집합을 활용했습니다.

분리집합이란, 각각의 값들에게 부모를 부여하고, 해당 부모는 그 자체로 하나의 집합을 의미하여, 각각의 값들을 집합으로 묶는 것을 의미합니다.

이 기법을 활용하게 되면, Log 스타의 속도로 본인이 어떤 집합에 속해있는지 찾을 수 있게되고, 그 집합의 길이만 정의해놓으면, 본인이 현재 속한 집합의 길이를 매우 빠르게 알 수 있습니다.

이를 행하기 위해서 다음과 같은 코드를 작성했습니다.

vi parent;
vi width;

int find(int x) {
	if (parent[x] == x) {
	  return x;
	}
	return parent[x] = find(parent[x]);
}

void uni(int high, int lower) {
	width[high] += width[find(parent[lower])];
	parent[lower] = high;
}

집합을 합칠 때(uni) 집합의 Width를 새롭게 정의해주고 (합칠 때, 자식 집합의 Width를 부모 집합에 더해줌), 이를 find 메서드를 통해 굉장히 빠르게 찾아줄 수 있습니다.

이렇게 분리집합 및 위에서 정한 수식을 통해서 문제를 해결할 수 있게 되었습니다.

이를 해결한 전체 코드는 아래에 명시해놓겠습니다.

시간 복잡도

O(n * log N) 입니다.

전체 코드

class Solution {
  public: 
  
  typedef vector < int > vi;
  typedef vector < vi > vii;
  typedef vector < bool > vb;
  
  struct comp {
    bool operator()(vi & o1, vi & o2) {
      return o1[0] > o2[0];
    }
  };
  
  vi parent;
  vi width;
  
  int find(int x) {
    if (parent[x] == x) {
      return x;
    }
    return parent[x] = find(parent[x]);
  }
  
  void uni(int high, int lower) {
    width[high] += width[find(parent[lower])];
    parent[lower] = high;
  }
 
  int minCapability(vector < int > & nums, int k) {
    priority_queue < vi, vii, comp > pq;
    int n = nums.size();
    parent = vi(n, 0);
    width = vi(n, 1);
    vb visited(n, false);
    for (int i = 0; i < n; i++) {
      pq.push({ nums[i], i });
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      parent[i] = i;
    }
    for (int i = 0; i < n; i++) {
      vi v = pq.top();
      pq.pop();
      int value = v[0];
      int position = v[1];
      visited[position] = true;

      int left = position - 1;
      int right = position + 1;
      int total = 0;

      if (left >= 0) {
        if (visited[left]) {
          total += (ceil(width[find(left)] / 2.0));
          uni(position, find(left));
        }
      }

      if (right < n) {
        if (visited[right]) {
          total += (ceil(width[find(right)] / 2.0));
          uni(position, find(right));
        }
      }

      cnt += (ceil(width[position] / 2.0) - total);

      if (cnt == k) {
        return value;
      }
    }
    return 0;
  }
};