'2025/02'에 해당되는 글 176건

Leetcode Problem:

• Find Score of an Array After Marking All Elements

Summary

• Given an array of positive integers, apply a scoring algorithm where the smallest unmarked integer is chosen, added to the score, and its adjacent elements are marked
• The process is repeated until all elements are marked.

Approach

• A priority queue (implemented as a heap) is used to store the unmarked elements along with their indices
• The heap is updated after each iteration to reflect the newly marked elements
• The algorithm iterates until the heap is empty, at which point the final score is returned.

Complexity

• O(n log n) due to the heap operations (insertion and deletion)

Solution Code:

struct _node{
    int idx;
    int val;
};

bool _cmp(_node a, _node b){
    if(a.val != b.val) return a.val < b.val;
    return a.idx < b.idx;
}

struct _heap{
    _node arr[100002];
    int size;
    _heap(){
        size = 1;
    }
    void push(_node a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && _cmp(arr[idx], arr[idx/2])){
            _node tmp = arr[idx/2];
            arr[idx/2] = arr[idx];
            arr[idx] = tmp;
            idx >>= 1;
        }
    }
    _node pop(){
        _node ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i*2;
            if(j >= size){
                break;
            }
            if(j+1 < size && _cmp(arr[j+1], arr[j])){
                j++;
            }
            if(_cmp(arr[j], arr[i])){
                _node t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;

            } else {
                break;
            }
        }

        return ret;

    }
    bool empty(){
        return size == 1;
    }
    _node peek(){
        return arr[1];
    }
};

class Solution {
public:
    _heap h;
    _heap remove;
    bool removed[100002];
    long long findScore(vector& nums) {
        for(int i = 0 ; i < nums.size(); i++){
            h.push({i, nums[i]});
        }
        long long sum = 0;
        while(!h.empty()){
            while(!h.empty() && h.peek().val == remove.peek().val && 
                                h.peek().idx == remove.peek().idx){
                remove.pop();
                h.pop();
            }
            if(h.empty()) break;
            _node nod = h.pop();
            cout << nod.val << endl;
            sum += nod.val;
            if(nod.idx -1 >= 0 && !removed[nod.idx-1]){
                removed[nod.idx-1] = true;
                remove.push({nod.idx-1, nums[nod.idx-1]});
            }
            if(nod.idx+1 < nums.size()  && !removed[nod.idx+1]){
                removed[nod.idx+1] = true;
                remove.push({nod.idx+1, nums[nod.idx+1]});
            }
        }
        return sum;
    }
};

Leetcode Problem:

• Take Gifts From the Richest Pile

Summary

• The problem requires to find the number of gifts remaining after k seconds, where each second, the maximum pile is chosen and its size is reduced to the floor of its square root.

Approach

• A heap data structure is used to store the number of gifts in each pile
• The pop operation is used to choose the maximum pile and reduce its size to the floor of its square root
• The process is repeated for k seconds.

Complexity

• O(n log n) due to the heap operations, where n is the number of piles.

Explanation

• The provided solution code first initializes a heap with the number of gifts in each pile
• Then, it enters a loop that runs for k seconds
• In each iteration, it pops the maximum pile from the heap, reduces its size to the floor of its square root, and pushes it back into the heap
• Finally, it calculates the total number of gifts remaining by summing up the sizes of all piles in the heap.

Solution Code:

struct _heap{
    int arr[1002];
    int size;
    _heap(){
        size = 1;
    }
    void push(int a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && arr[idx] > arr[idx/2]){
            int t = arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = t;
            idx/=2;
        }
    }
    int pop(){
        int ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if(j>= size) break;
            if(j+1 < size && arr[j] < arr[j+1]){
                j++;
            }
            if(arr[i] < arr[j]){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else {
                break;
            }
        }


        return ret;
    }
};

class Solution {
public:
    _heap h;
    long long pickGifts(vector& gifts, int k) {
        for(int i = 0 ; i < gifts.size(); i++){
            h.push(gifts[i]);
        }
        while(k--){
            int gift = h.pop();
            int i = 1;
            while(i*i <= gift) i++;
            i--;
            h.push(i);
        }
        long long sum = 0;
        for(int i = 1; i < h.size; i++){
            sum += h.arr[i];
        }
        return sum;
    }
};

Leetcode Problem:

• Maximum Beauty of an Array After Applying Operation

Summary

• Given a 0-indexed array nums and a non-negative integer k, find the maximum possible beauty of the array after applying the operation any number of times.

Approach

• This problem can be solved by using a two-pointer technique
• The idea is to maintain two pointers, one at the beginning and one at the end of the array
• The pointer at the end is used to track the maximum possible beauty
• The pointer at the beginning is used to track the minimum possible value in the current window
• If the difference between the value at the end pointer and k is less than or equal to the sum of the value at the beginning pointer and k, it means that we can extend the current window to the right
• Otherwise, we move the beginning pointer to the right.

Complexity

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

Explanation

• The solution starts by sorting the input array in ascending order
• Then it initializes two pointers, l and r, to 0
• It also initializes a variable ans to 1
• The while loop continues until the end pointer r reaches the end of the array
• Inside the loop, it checks if the difference between the value at the end pointer and k is less than or equal to the sum of the value at the beginning pointer and k
• If the condition is true, it means that we can extend the current window to the right, so it increments the end pointer r and updates the ans variable with the maximum of the current ans and the difference between the end pointer r and the beginning pointer l
• Otherwise, it increments the beginning pointer l
• Finally, the solution returns the ans variable, which represents the maximum possible beauty of the array.

Solution Code:

class Solution {
public:
    int maximumBeauty(vector& nums, int k) {
        sort(nums.begin(), nums.end());
        int l = 0;
        int r = 0;
        int ans = 1;
        while(r < nums.size()){
            if(nums[r] - k <= nums[l] + k){
                r++;
                ans = max(ans, r - l);
            } else{
                l++;
            }
        }
        
        
        return ans;
    }
};

Leetcode Problem:

• Find Longest Special Substring That Occurs Thrice I

Summary

• Find the length of the longest special substring of a given string that occurs at least thrice, or return -1 if no such substring exists.

Approach

• Use binary search to find the longest special substring that occurs at least thrice
• The approach involves checking for the presence of a special character (a single character) in the string and counting its occurrences
• If a special character is found to occur at least thrice, the approach updates the binary search range to focus on the longer special substrings.

Complexity

• O(n log m) where n is the length of the string and m is the range of possible special characters (26 lowercase English letters)

Explanation

• The solution uses binary search to efficiently find the longest special substring that occurs at least thrice
• The binary search range is initially set to the entire string, and the approach iteratively narrows down the range to focus on longer special substrings
• The approach checks for the presence of a special character in the string and counts its occurrences
• If a special character is found to occur at least thrice, the approach updates the binary search range to focus on the longer special substrings
• The process is repeated until the longest special substring that occurs at least thrice is found, or the binary search range becomes empty.

Solution Code:

class Solution {
public:
    int maximumLength(string s) {
        int ans = -1;
        int l = 1;
        int r = s.size()-2;
        
        while(l <= r){
            int mid = (l + r) >> 1;
            bool success = false;
            for(char i = 'a'; i <= 'z'; i++){
                int k = 0;
                int specialCnt = 0;
                for(int j = 0; j < s.size(); j++){
                    if(s[j] == i){
                        k++;
                    } else{
                        k = 0;
                    }
                    if(k == mid){
                        k--;
                        specialCnt++;
                        if(specialCnt >= 3){
                            success = true;
                            break;
                        }
                    }
                }
                if(success) break;
            }
            if(success){
                l = mid + 1;
                ans = mid;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Special Array II

Summary

• Check if every pair of adjacent elements in an array contains numbers with different parity.

Approach

• Use a prefix sum array to store the parity of each element in the array
• Then for each query, check if the difference between the parity at the end and start indices is equal to the number of elements in the query
• If it is, the subarray is special.

Complexity

• O(n + q) where n is the size of the array and q is the number of queries.

Explanation

• The solution uses a prefix sum array to store the parity of each element in the array
• The parity is 1 if the number is odd and 0 if the number is even
• The prefix sum array is updated by adding 1 to the parity if the current number is even and the previous number is odd, or if the current number is odd and the previous number is even
• Then for each query, the difference between the parity at the end and start indices is calculated
• If the difference is equal to the number of elements in the query, the subarray is special
• Otherwise, it is not special.

Solution Code:

class Solution {
public:
    vector isArraySpecial(vector& nums, vector>& queries) {
        vector ans;
        vector memo;
        memo.push_back(1);
        for(int i = 1 ; i < nums.size(); i++){
            int num = memo.back();
            if(nums[i] %2 == nums[i-1] %2){
                memo.push_back(num);
            } else{
                memo.push_back(num+1);
            }
        }
        for(int i =  0; i < queries.size(); i++){
            int a = queries[i][0];
            int b = queries[i][1];
            if(b- a == memo[b] - memo[a]){
                ans.push_back(true);
            } else {
                ans.push_back(false);
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Most Profitable Path in a Tree

Summary

• The problem is to find the maximum net income that Alice can have if she travels towards the optimal leaf node in an undirected tree.

Approach

• The approach used is to use a depth-first search (DFS) traversal to find the optimal leaf node
• The DFS traversal is performed in two phases: first, to find the optimal leaf node for Bob, and second, to find the maximum net income for Alice
• The optimal leaf node for Bob is found by traversing the tree from node 0 and updating the amount array accordingly
• The maximum net income for Alice is then found by traversing the tree from the optimal leaf node and updating the sum variable accordingly.

Complexity

• O(n log n) due to the sorting of the amount array

Explanation

• The solution code first initializes the adjacency list and visited arrays
• It then defines two helper functions: goBobAndUpdateAmount and dfs
• The goBobAndUpdateAmount function performs the DFS traversal from node 0 to find the optimal leaf node for Bob, while the dfs function performs the DFS traversal from the optimal leaf node to find the maximum net income for Alice
• The solution code then calls the goBobAndUpdateAmount function to find the optimal leaf node for Bob, and then calls the dfs function to find the maximum net income for Alice
• The maximum net income for Alice is then returned as the result.

Solution Code:

class Solution {
    vector adj[100001];
    bool visited[100001] = {false,};
    bool visited2[100001] = {false,};
    bool isLeaf[100001] = {false,};
    int ans = -1000000001;
public:

    int goBobAndUpdateAmount(int node, int depth, int bob, vector& amount){
        if(visited[node]) return 100001;
        if(node == bob){
            amount[node] = 0;
            return depth;
        }
        visited[node] = true;
        int distanceBob = 100001;
        for(int i = 0 ; i < adj[node].size(); i++){
            int next = adj[node][i];
            distanceBob = goBobAndUpdateAmount(next, depth + 1, bob, amount);
            if(distanceBob == 100001) continue;
            if(depth > (distanceBob/2)){
                amount[node] = 0;
            } 
            if(depth == (distanceBob/2) && distanceBob %2 == 0){
                amount[node]/=2;
            }
            break;
        }
        return distanceBob;
    }
    void dfs(int node, int sum, vector& amount){
        if(visited2[node]) return;
        visited2[node] = true;
        sum += amount[node];
        if(isLeaf[node] && ans < sum){
            ans = sum;
        }
        for(int i = 0 ; i < adj[node].size(); i++){
            int next = adj[node][i];
            dfs(next, sum, amount);
        }
    }
    int mostProfitablePath(vector>& edges, int bob, vector& amount) {
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        for(int i = 1; i <= edges.size(); i++){
            if(adj[i].size() == 1) isLeaf[i] = true;
        }
        goBobAndUpdateAmount(0, 0, bob, amount);
        
        dfs(0, 0, amount);
        return ans;
    }
};

Leetcode Problem:

• Two Best Non-Overlapping Events

Summary

• Given a 2D array of events where each event has a start time, end time, and value, find the maximum sum of two non-overlapping events.

Approach

• The approach is to first sort the events by their start time, then use dynamic programming to find the maximum sum of two non-overlapping events
• We also use a suffix maximum array to store the maximum value that can be obtained by attending the events up to each index.

Complexity

• O(n log n) due to the sorting of events, where n is the number of events.

Solution Code:

class Solution {
public:
    int maxTwoEvents(vector>& events) {
        int n = events.size();
        
        sort(events.begin(), events.end(), [](const vector& a, const vector& b) {
            return a[0] < b[0];
        });
        
        vector suffixMax(n);
        suffixMax[n - 1] = events[n - 1][2];
        
        for (int i = n - 2; i >= 0; --i) {
            suffixMax[i] = max(events[i][2], suffixMax[i + 1]);
        }
        
        int maxSum = 0;
        
        for (int i = 0; i < n; ++i) {
            int left = i + 1, right = n - 1;
            int nextEventIndex = -1;
            
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (events[mid][0] > events[i][1]) {
                    nextEventIndex = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            if (nextEventIndex != -1) {
                maxSum = max(maxSum, events[i][2] + suffixMax[nextEventIndex]);
            }
            
            maxSum = max(maxSum, events[i][2]);
        }
        
        return maxSum;
    }
};

Leetcode Problem:

• Minimum Limit of Balls in a Bag

Summary

• Find the minimum possible penalty after performing operations on bags of balls.

Approach

• Binary search approach to find the minimum possible penalty
• The idea is to perform binary search on the possible maximum number of balls in a bag
• The binary search is performed on the range [1, max balls in a bag]
• For each mid value, it checks if the number of operations required to divide all bags into smaller bags is less than or equal to maxOperations
• If it is, then the minimum possible penalty is updated and the search space is narrowed down to the lower half of the range
• If not, the search space is narrowed down to the upper half of the range.

Complexity

• O(n log m) where n is the number of bags and m is the maximum number of balls in a bag.

Explanation

• The solution uses a binary search approach to find the minimum possible penalty
• The binary search is performed on the possible maximum number of balls in a bag, which is represented by the variable mid
• For each mid value, it checks if the number of operations required to divide all bags into smaller bags is less than or equal to maxOperations
• If it is, then the minimum possible penalty is updated and the search space is narrowed down to the lower half of the range
• If not, the search space is narrowed down to the upper half of the range
• This process is repeated until the minimum possible penalty is found.

Solution Code:

class Solution {
public:
    
    
    int minimumSize(vector& nums, int maxOperations) {
        int _max = 0;
        for(int i = 0 ; i < nums.size(); i++){
            if (_max < nums[i]){
                _max = nums[i];
            }
        }
        int l = 1; 
        int r = _max;
        int ans = _max;
        while(l <= r){
            int mid = l + (r - l)/2;
            cout << mid << endl;
            int operation = maxOperations;
            bool success = true;
            for(int i = 0 ; i < nums.size(); i++){
                if(mid < nums[i]){
                    operation -= ((nums[i] + mid - 1) / mid) - 1;
                }
                if(operation < 0){
                    success = false;
                    break;
                }
            }
            if(success){
                r = mid -1;
                ans = mid;
            } else{
                l= mid + 1;
            }

        }        

        return ans;
    }
};

Leetcode Problem:

• Maximum Number of Integers to Choose From a Range I

Summary

• Find the maximum number of integers that can be chosen from the range [1, n] without exceeding maxSum and without being in the banned array.

Approach

• The approach used is to first create a boolean array ban to mark the banned numbers, then create a vector nums to store the available numbers, and finally use two pointers to find the maximum sum that does not exceed maxSum.

Complexity

• O(n + banned.length) where n is the range [1, n] and banned.length is the number of banned numbers

Explanation

• The code first initializes a boolean array ban to mark the banned numbers and a vector nums to store the available numbers
• Then it iterates over the banned numbers and marks them in the ban array
• After that, it iterates over the range [1, n] and adds the available numbers to the nums vector
• Finally, it uses two pointers to find the maximum sum that does not exceed maxSum by iterating over the nums vector and adding the current number to the sum
• If the sum exceeds maxSum, it breaks the loop and returns the number of available numbers that were added to the sum.

Solution Code:

class Solution {
public:
    vector nums;
    bool ban[10001];
    int maxCount(vector& banned, int n, int maxSum) {
        for(int i = 0 ; i < banned.size(); i++){
            ban[banned[i]] = true;
        }
        for(int i = 1; i <= n; i++){
            if(ban[i]) continue;
            nums.push_back(i);
        }
        int sum = 0;
        int ans = 0;
        for(int i = 0 ; i < nums.size(); i++){
            sum += nums[i];
            if(sum > maxSum) break;
            ans++;
        }
        return ans;
    }
};

Leetcode Problem:

• Move Pieces to Obtain a String

Summary

• Check if a string can be transformed into another string by moving pieces (L, R, _) a certain number of times.

Approach

• This solution uses a two-pointer approach to iterate over both strings simultaneously
• It checks for the next available position for each piece in both strings and moves them accordingly
• If a piece cannot be moved to its next position, it returns false
• If all pieces can be moved to their next positions, it checks if both strings have been fully traversed and returns true if so, otherwise false.

Complexity

• O(n), where n is the length of the input strings.

Explanation

• The solution defines two helper functions, `nextCharIdx`, to find the next available position for each piece in both strings
• It then iterates over both strings using two pointers, `idx1` and `idx2`, which start at the beginning of each string
• It checks if the current positions in both strings match, and if they do, it moves the pieces to the next position
• If a piece cannot be moved to its next position, it returns false
• If all pieces can be moved to their next positions, it checks if both strings have been fully traversed and returns true if so, otherwise false.

Solution Code:

class Solution {
public:
    int nextCharIdx(string& str, int idx){
        for(int i = idx; i < str.size(); i++){
            if(str[i] == 'L' || str[i] == 'R') return i;
        }
        return str.size();
    }
    bool canChange(string start, string target) {
        int idx1, idx2;
        idx1 = idx2 = 0;
        while(true){
            idx1 = nextCharIdx(start, idx1);
            idx2 = nextCharIdx(target, idx2);
            if(idx1 == start.size() || idx2 == target.size()){       
                break;
            }
            if(start[idx1] != target[idx2]) return false;
            if(start[idx1] == 'L'){
                if(idx1 < idx2){
                    return false;
                }
            }
            if(start[idx1] == 'R'){
                if(idx1 > idx2){
                    return false;
                }
            }
            idx1++;
            idx2++;
        }
        if(idx1 == start.size() && idx2 == target.size()){
            return true;
        }
        return false;
    }
};