'알고리즘'에 해당되는 글 246건

Leetcode Problem:

• Minimum Operations to Make Array Values Equal to K

Summary

• The problem requires to find the minimum number of operations required to make every element in the array equal to a given number k
• An operation is defined as selecting a valid integer h for the current values in the array, and for each index i where nums[i] > h, set nums[i] to h.

Approach

• The solution sorts the input array and checks if the first element is less than k
• If it is, the function returns -1
• Otherwise, it initializes a counter cnt and a variable cur to the first element of the array
• It then iterates over the array, incrementing cnt whenever it encounters an element different from cur
• Finally, it returns cnt as the minimum number of operations required.

Complexity

• O(n log n) due to the sorting operation, where n is the size of the input array.

Explanation

• The provided solution code uses a simple and efficient approach to solve the problem
• First, it sorts the input array in ascending order
• If the first element is less than k, the function returns -1, indicating that it is impossible to make all elements equal to k
• Otherwise, it initializes a counter cnt and a variable cur to the first element of the array
• It then iterates over the array, incrementing cnt whenever it encounters an element different from cur
• Finally, it returns cnt as the minimum number of operations required
• The time complexity of this solution is O(n log n) due to the sorting operation, where n is the size of the input array.

Solution Code:

class Solution {
public:
    int minOperations(vector& nums, int k) {
        sort(nums.begin(), nums.end());
        if(nums[0] < k) return -1;
        int cnt = 0;
        int cur = nums[0];
        if(cur != k) cnt++;
        for(int i = 1; i < nums.size(); i++){
            if(cur != nums[i]){
                cnt++;
                cur = nums[i];
            }
        }
        return cnt;
    }
};

Leetcode Problem:

• Minimum Number of Operations to Make Elements in Array Distinct

Summary

• The problem is to find the minimum number of operations needed to make the elements in the array distinct
• The operation allowed is to remove 3 elements from the beginning of the array
• The goal is to return the minimum number of operations required to make all elements in the array distinct.

Approach

• The approach used is to first count the occurrences of each number in the array
• Then, if a number occurs more than once, we find the last occurrence of that number and calculate the minimum number of operations required to remove all occurrences of that number
• The minimum number of operations is calculated by dividing the last occurrence index by 3 and adding 1.

Complexity

• O(n) where n is the size of the array, because we are scanning the array once to count the occurrences of each number.

Explanation

• The code first initializes a count array `numberCnt` to keep track of the occurrences of each number in the array
• It then scans the array from the end to the beginning and increments the count of each number in the `numberCnt` array
• If a number occurs more than once, it updates the `lastIdx` variable to the last occurrence index of that number
• Finally, it calculates the minimum number of operations required by dividing the `lastIdx` by 3 and adding 1, and returns this value.

Solution Code:

class Solution {
public:
    int numberCnt[101];
    int minimumOperations(vector& nums) {
        int lastIdx = -1;
        for(int i = nums.size() - 1 ; i >= 0 ; i--){
            numberCnt[nums[i]]++;
            if(numberCnt[nums[i]] >= 2){
                lastIdx = i;
                break;
            }
        }
        if(lastIdx == -1) return 0;
        return lastIdx / 3 + 1;
    }
};

Leetcode Problem:

• Partition Equal Subset Sum

Summary

• Given an integer array, determine if it can be partitioned into two subsets with equal sum.

Approach

• Dynamic Programming: The solution uses a dynamic programming approach to build a table (dp) where dp[i] represents whether the sum of the first i elements can be achieved
• The solution iterates through the array, updating the dp table and checking for the target sum.

Complexity

• O(n * targetSum) where n is the length of the array and targetSum is the target sum

Explanation

• The solution first calculates the total sum of the array and checks if it is even
• If it is not, the array cannot be partitioned into two subsets with equal sum
• Otherwise, it initializes a dynamic programming table dp of size targetSum + 1, where dp[i] represents whether the sum of the first i elements can be achieved
• It then iterates through the array, updating the dp table and checking for the target sum
• If the target sum can be achieved, the function returns true
• If not, the function returns false.

Solution Code:

class Solution {
public:
    bool canPartition(vector& nums) {
        int totalSum = 0;
        for (int num : nums) totalSum += num;

        if (totalSum % 2 != 0) return false;

        int targetSum = totalSum / 2;
        vector dp(targetSum + 1, false);
        dp[0] = true;
        for (int num : nums) {
            for (int currSum = targetSum; currSum >= num; --currSum) {
                dp[currSum] = dp[currSum] || dp[currSum - num];
                if (dp[targetSum]) return true;
            }
        }
        return dp[targetSum];
    }
};

Leetcode Problem:

• Largest Divisible Subset

Summary

• Given a set of distinct positive integers, find the largest subset such that every pair of elements in the subset satisfies either element is divisible by the other.

Approach

• Dynamic Programming: The solution uses a dynamic programming approach to build a table (dp) where dp[i] represents the length of the longest divisible subset ending at index i
• The solution also maintains a table (prev_idx) to keep track of the previous element in the longest divisible subset ending at each index.

Complexity

• O(n^2), where n is the number of elements in the input array

Explanation

• The solution first sorts the input array and initializes the dp and prev_idx tables
• It then iterates over the array, updating the dp and prev_idx tables to build the longest divisible subset
• Finally, it iterates over the dp table to find the index of the longest divisible subset and constructs the answer vector by backtracking from that index.

Solution Code:

class Solution {
public:
    int dp[1001];
    int prev_idx[1001];
    vector largestDivisibleSubset(vector& nums) {
        // dp
        sort(nums.begin(), nums.end());
        for(int i = 0 ; i < nums.size(); i++){
            dp[i] = 1;
            prev_idx[i] = -1;
        }
        for(int i = 0 ; i < nums.size(); i++){
            for(int j = i - 1 ; j >= 0; j--){
                if((dp[j]+1) > dp[i] && (nums[i] % nums[j]) == 0){
                    dp[i] = dp[j] + 1;
                    prev_idx[i] = j;
                }
            }
        }
        int max = 0;
        int idx = 0;
        for(int i = 0; i < nums.size(); i++){
            if(max < dp[i]){
                max = dp[i];
                idx = i;
            }
        }
        vector ans;
        while(idx != -1){
            ans.push_back(nums[idx]);
            idx = prev_idx[idx];
        }
        return ans;
    }
};

Leetcode Problem:

• Sum of All Subset XOR Totals

Summary

• The problem requires finding the sum of all XOR totals for every subset of the given array.

Approach

• The approach used is a recursive function that tries all possible subsets by either including or excluding the current element in the subset.

Complexity

• O(2^n * n) where n is the number of elements in the array

Explanation

• The solution uses a recursive function to generate all possible subsets
• For each subset, it calculates the XOR total by XORing all elements in the subset
• The base case is when the current index is out of bounds, in which case the XOR total is added to the result
• The function is called recursively with the next index and the XOR total of the current element
• The time complexity is O(2^n * n) because in the worst case, we have to generate all possible subsets and calculate the XOR total for each subset.

Solution Code:

class Solution {
public:
    int ans = 0;
    void go(int cur, int sum, vector& nums){
        if(cur >= nums.size()) {
            ans += sum;
            return;
        }
        go(cur + 1, sum ^ nums[cur], nums );
        go(cur + 1, sum, nums );
    }
    int subsetXORSum(vector& nums) {
        go(0, 0, nums);
        return ans;
    }
};

Leetcode Problem:

• Lowest Common Ancestor of Deepest Leaves

Summary

• The problem is to find the lowest common ancestor of the deepest leaves in a binary tree.

Approach

• The solution uses a depth-first search (DFS) traversal to find the deepest leaves
• It keeps track of the maximum depth and the nodes at that depth
• Then, it iteratively checks if the nodes at the maximum depth are the deepest leaves by checking if their parent nodes are the same
• If they are, it returns the parent node
• Otherwise, it updates the list of deepest leaves and continues the process until it finds the lowest common ancestor.

Complexity

• O(n), where n is the number of nodes in the tree

Explanation

• The solution uses a recursive DFS traversal to find the deepest leaves
• It keeps track of the maximum depth and the nodes at that depth using a vector
• It also uses a parent array to keep track of the parent nodes of each node
• The traversal function updates the maximum depth and the list of deepest leaves as it traverses the tree
• The lcaDeepestLeaves function iteratively checks if the nodes at the maximum depth are the deepest leaves by checking if their parent nodes are the same
• If they are, it returns the parent node
• Otherwise, it updates the list of deepest leaves and continues the process until it finds the lowest common ancestor.

Solution Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth = -1;
    TreeNode* parent[1001];
    vector list;
    void traversal(TreeNode* root, int depth){
        if(root == nullptr) return;
        if(maxDepth < depth){
            maxDepth = depth;
            list.clear();
            list.push_back(root);
        } else if(maxDepth == depth){
            list.push_back(root);
        }
        if(root->left) parent[root->left->val] = root;
        if(root->right) parent[root->right->val] = root;
        traversal(root->left, depth + 1);
        traversal(root->right, depth + 1);
    }
    TreeNode* lcaDeepestLeaves(TreeNode* root) {
        traversal(root, 0);
        
        while(true){
            if (list.size() == 1) return list[0];
            vector tmp;
            bool success = true;
            int goal = parent[list[0]->val]->val;
            for(int i = 0 ; i < list.size(); i++){
                tmp.push_back(parent[list[i]->val]);
                if(goal != parent[list[i]->val]->val){
                    success = false;
                }
            }
            if(success) return tmp[0];
            list.clear();
            list = tmp;
        }
        return nullptr;
    }
};

Leetcode Problem:

• Maximum Value of an Ordered Triplet II

Summary

• Find the maximum value over all triplets of indices (i, j, k) such that i < j < k in the given array nums.

Approach

• The approach used is to use a stack to store the elements of the array
• We iterate over the array and for each element, we update the maximum distance between the smallest and largest elements in the stack
• We also update the maximum value by multiplying the maximum distance with the current element
• If the current element is greater than the top of the stack, we remove elements from the stack until the top of the stack is less than or equal to the current element
• Finally, we return the maximum value found.

Complexity

• O(n log n) due to the sorting operation inside the while loop

Explanation

• The solution code uses a stack to store the elements of the array
• We iterate over the array and for each element, we update the maximum distance between the smallest and largest elements in the stack
• We also update the maximum value by multiplying the maximum distance with the current element
• If the current element is greater than the top of the stack, we remove elements from the stack until the top of the stack is less than or equal to the current element
• This is done to ensure that the stack always contains the smallest and largest elements seen so far
• Finally, we return the maximum value found.

Solution Code:

class Solution {
public:

    long long maximumTripletValue(vector& nums) {
        long long ans = 0;
        int maxDist = 0;
        vector st;

        for(int i = 0; i < nums.size(); i++){
            if(st.size() >= 2){
                maxDist = max(maxDist, st[0] - st.back());
            }
            ans = max(ans, (long long)maxDist * nums[i]);
            while(!st.empty() && st.back() < nums[i]){
                st.pop_back();
            }
            st.push_back(nums[i]);
        }
        return ans;
    }
};

Leetcode Problem:

• Maximum Value of an Ordered Triplet I

Summary

• The problem requires finding the maximum value of a triplet of indices (i, j, k) in a given array such that i < j < k, and the value of the triplet is (nums[i] - nums[j]) * nums[k].

Approach

• The approach used is a recursive combination of elements from the array to form triplets, and the maximum value is updated accordingly.

Complexity

• O(n^3) due to the recursive combination of elements and the use of a vector to store selected elements.

Explanation

• The solution uses a recursive function combi() to generate all possible triplets of indices and calculate their values
• The function takes the current index, depth, and a vector of selected elements as parameters
• If the depth is 3, the function updates the maximum value if the current triplet has a greater value
• Otherwise, it recursively calls itself for the next index and increments the depth
• The function also uses backtracking to explore all possible combinations of elements by popping the last element from the vector and restoring the previous state.

Solution Code:

class Solution {
public:
    long long ans = 0;
    void combi(vector&nums, int cur, int depth, vector& selected){
        if(depth == 3){
            ans = max(ans, (selected[0] - selected[1])*selected[2]);
            return;
        }
        for(int i = cur + 1; i < nums.size(); i++){
            selected.push_back(nums[i]);
            combi(nums, i, depth + 1, selected);
            selected.pop_back();
        }
    }
    long long maximumTripletValue(vector& nums) {
        vector selected;
        combi(nums,-1, 0, selected);
        return ans;
    }
};

Leetcode Problem:

• Solving Questions With Brainpower

Summary

• Given a 2D array of questions where each question has a point value and a brainpower value, find the maximum points that can be earned by solving the questions in order.

Approach

• Dynamic Programming: The problem can be solved using dynamic programming
• The idea is to maintain a memoization table to store the maximum points that can be earned for each question
• The function iterates over the questions in reverse order and for each question, it calculates the maximum points that can be earned by either solving the current question or skipping it.

Complexity

• O(N) where N is the number of questions, as each question is visited once.

Solution Code:

class Solution {
public:
    long long memo[200001] = {0};
    long long mostPoints(vector>& questions) {
        int N = questions.size();
        for(int i = N - 1; i >= 0; i--){
            int point = questions[i][0];
            int brainpower = questions[i][1];
            memo[i] = max(point + memo[i + brainpower + 1], memo[i+1]);
        }
        return memo[0];
    }
};

Leetcode Problem:

• Put Marbles in Bags

Summary

• The problem requires finding the difference between the maximum and minimum scores of marble distributions given an array of weights and the number of bags.

Approach

• The solution uses a prefix sum array to efficiently calculate the sum of weights for each subarray
• It then sorts the prefix sum array and iterates through it to calculate the minimum and maximum scores by adding the weights at specific indices
• The difference between the maximum and minimum scores is then returned.

Complexity

• O(n log n) due to the sorting of the prefix sum array, where n is the number of weights.

Solution Code:

class Solution {
public:
    long long putMarbles(vector& weights, int k) {
        if(weights.size() == k) return 0;
        vector prefixSum;
        long long sum = weights[0];
        for(int i = 1 ; i < weights.size(); i++){
            sum += weights[i];
            prefixSum.push_back(sum);
            sum -= weights[i-1];
        }
        sort(prefixSum.begin(), prefixSum.end());

        long long maxScore = weights[0] + weights[weights.size() - 1];
        long long minScore = weights[0] + weights[weights.size() - 1];
        for(int i = 0; i < k - 1; i++){
            minScore += prefixSum[i];
            maxScore += prefixSum[prefixSum.size() - 1 - i];
        }

        return maxScore - minScore;
    }
};