Removing Minimum Number of Magic Beans[M,Array,Greedy,Sorting,Enumeration,Prefix Sum]

https://leetcode.com/problems/removing-minimum-number-of-magic-beans/description/

You are given an array of positive integers beans, where each integer represents the number of magic beans found in a particular magic bag.

Remove any number of beans (possibly none) from each bag such that the number of beans in each remaining non-empty bag (still containing at least one bean) is equal. Once a bean has been removed from a bag, you are not allowed to return it to any of the bags.

Return the minimum number of magic beans that you have to remove.

 

Example 1:

Input: beans = [4,1,6,5]
Output: 4
Explanation: 
- We remove 1 bean from the bag with only 1 bean.
  This results in the remaining bags: [4,0,6,5]
- Then we remove 2 beans from the bag with 6 beans.
  This results in the remaining bags: [4,0,4,5]
- Then we remove 1 bean from the bag with 5 beans.
  This results in the remaining bags: [4,0,4,4]
We removed a total of 1 + 2 + 1 = 4 beans to make the remaining non-empty bags have an equal number of beans.
There are no other solutions that remove 4 beans or fewer.

Example 2:

Input: beans = [2,10,3,2]
Output: 7
Explanation:
- We remove 2 beans from one of the bags with 2 beans.
  This results in the remaining bags: [0,10,3,2]
- Then we remove 2 beans from the other bag with 2 beans.
  This results in the remaining bags: [0,10,3,0]
- Then we remove 3 beans from the bag with 3 beans. 
  This results in the remaining bags: [0,10,0,0]
We removed a total of 2 + 2 + 3 = 7 beans to make the remaining non-empty bags have an equal number of beans.
There are no other solutions that removes 7 beans or fewer.

 

Constraints:

• 1 <= beans.length <= 105
• 1 <= beans[i] <= 105

1. Python

 

- 오답.. GG다

class Solution:
    def minimumRemoval(self, beans: List[int]) -> int:

        beans.sort()
        ans = 0 
        for i in range(len(beans)):
            temp = beans[i]
            if temp < sum(beans[i+1:])-temp*(len(beans)-(i+1)):
                ans += temp
                continue
            else:
                while i<len(beans)-1:
                    ans += beans[i+1] - temp
                    i+=1
                break
        return ans

 

- GPT 참고..

class Solution:
    def minimumRemoval(self, beans: List[int]) -> int:
        beans.sort()
        total_beans = sum(beans)
        n = len(beans)
        min_removal = float('inf')
        
        for i, b in enumerate(beans):
            current_removal = total_beans - (n - i) * b
            min_removal = min(min_removal, current_removal)
        
        return min_removal

 

머리의 한계를 느낀다. 아 진짜 어렵네..

class Solution:
    def minimumRemoval(self, beans: List[int]) -> int:
        beans.sort()
        total_beans = sum(beans)
        prefix_sum = 0
        min_removal = float('inf')

        for i in range(len(beans)):
            current_beans = beans[i]
            prefix_sum += current_beans
            remaining_beans = total_beans - prefix_sum
            removal = remaining_beans - (len(beans) - i - 1) * current_beans
            min_removal = min(min_removal, removal)

        return min_removal

이해하는데 한 참 걸렸네

 

이거 그냥 수학 올림피아드 문제같다.

 

거지같은 알고리즘 ㅜㅜ 이게 수학문제지 코딩문제냐!

 

2. C

 

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);}

long long minimumRemoval(int* beans, int beansSize) {
    long long minval = LLONG_MAX;
    long long sum = 0;
    for(int i=0;i<beansSize;i++){
        sum+=beans[i];
    }

    //C-insertion sorting
    // for(int i=1;i<beansSize;i++){
    //     int temp = beans[i];
    //     int j = i-1;
        
    //     while(j>=0 && temp<beans[j]){
    //         beans[j+1] = beans[j];
    //         j--;
    //     }
    //     beans[j+1] = temp;
    // }
    qsort(beans, beansSize, sizeof(int), compare);    
    for(int j=0;j<beansSize;j++){
        long long current = sum - (long long)beans[j]*(beansSize-j);
        if(minval > current) minval = current;
    }
    return minval;
}

 

sort에 사용된 나의 귀여운 insertion sort는 크기가 큰 input에 대해선 time limint이 걸렸다.

 

3. C++

맥락은 비슷하다. 다만 C에 비해 sorting 기능이 추가된 것에 감사하며..

 

class Solution {
public:
    long long minimumRemoval(vector<int>& beans) {
        int n = beans.size();
        long long sum = 0;
        for(const int a: beans){
            sum +=a;
        }
        sort(beans.begin(),beans.end());

        long long minval = LLONG_MAX;

        for(int i=0; i<n; i++){
            long long current = sum - (long long)beans[i]*(n-i);
            if(minval > current) minval=current;
        }
        return minval;
    }
};