LeetCode Weekly Contest 230

A. Count Items Matching a Rule

입력으로 주어지는 items배열에서 rulekey와 ruleValue에 맞는 항목의 개수를 리턴하는 문제이다.

class Solution {
public:
    int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {
        int find;
        if(ruleKey=="type") find=0;
        else if(ruleKey=="color") find=1;
        else find=2;
        int ans=0;
        for(vector<string> it : items) {
            if(it[find]==ruleValue) ans++;
        }
        return ans;
    }
};

---

B. Closest Dessert Cost

주어진 base와 toppingCosts를 조합하여 아이스크림 가격을 target에 가깝게 만드는 문제이다.

완전탐색을 사용하여 해결할 수 있다.

class Solution {
public:
    int n,m;
    set<pair<int,int>> s;
    void dfs(int cur, int base, vector<int> &cnt, vector<int> &toppingCosts,int target) {
        int sum=base;
        for(int i=0;i<m;i++) {
            sum+=toppingCosts[i]*cnt[i];
        }
        s.insert({abs(target-sum),sum});
        
        for(int i=cur;i<m;i++) {
            if(cnt[i]<2) {
                cnt[i]++;
                dfs(i,base,cnt,toppingCosts,target);
                cnt[i]--;
            }
        }
    }
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
        n=baseCosts.size(),m=toppingCosts.size();
        for(int i=0;i<n;i++) {
            int base=baseCosts[i];
            s.insert({abs(target-base),base});
            vector<int> cnt(m,0);
            dfs(0,base,cnt,toppingCosts,target);
        }
        
        auto it=s.begin();
        int ret=it->second;
        
        return ret;
    }
};

---

C. Equal Sum Arrays With Minimum Number of Operations

nums1의 합계와 nums2의 합계가 같게 하기 위해 배열의 원소를 1과 6사의 자연수로 변경할 수 있는데 이런 연산의 최솟값을 구하는 문제이다.

각 배열의 합계 차이를 구해준다. 그 후에 각 배열의 원소들을 1 또는 6으로 변하게 하는 비용(?)의 수를 구해준다. (비용의 범위는 0과 5사이가 된다.)

두 배열의 합계 차이를 비용을 내림차순으로 깎아 없애는 방법으로 최솟값을 구해준다.

class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        if (nums2.size() * 6 < nums1.size() || nums1.size() * 6 < nums2.size()) return -1;
        
        int sum1=accumulate(nums1.begin(),nums1.end(),0);
        int sum2=accumulate(nums2.begin(),nums2.end(),0);
        int diff=abs(sum1-sum2);
        int ret=0;
        int cnt[6]={};
        
        if(sum1>sum2) swap(nums1,nums2);
        for(auto n : nums1) cnt[6-n]++; // 작은 원소들을 가진 배열을 6으로 만드는 비용(?)의 수
        for(auto n : nums2) cnt[n-1]++; // 큰 원소들을 가진 배열을 1로 만드는 비용(?)의 수
        
        for(int i=5;i>0 && diff>=0;i--) { // 비용(?)이 큰 수부터 시작해서 diff를 줄여준다
            int tmp=min(cnt[i],diff/i+(diff%i!=0));
            diff-=tmp*i;
            ret+=tmp;
        }
        
        return ret;
    }
};

---

D. Car Fleet II