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

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;
    }
};

Leetcode Problem:

• Partition Labels

Summary

• Partitioning a string into parts where each letter appears in at most one part

Approach

• Use a hashmap to store the last index of each character, then iterate through the string, updating the end index and adding the current part size to the result vector when the end index matches the current index

Complexity

• O(n) where n is the length of the string

Explanation

• The approach is to first store the last index of each character in a hashmap
• Then, we iterate through the string, updating the end index whenever we encounter a character
• When the end index matches the current index, we know we've reached the end of the current part, so we add its size to the result vector and reset the start and end indices
• This way, we ensure that each letter appears in at most one part and that the resultant string is the original input string

Solution Code:

class Solution {
public:
    int lastIdx[256];
    vector partitionLabels(string s) {
        for(int i = 0 ; i < s.size(); i++){
            lastIdx[s[i]] = i;
        }

        vector ans;
        int start = 0;
        int end = 0;
        for(int i = 0 ; i < s.size(); i++){
            end = max(end, lastIdx[s[i]]);
            if(end == i){
                ans.push_back(end - start + 1);
                start = end = end +1;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Apply Operations to Maximize Score

Summary

• The problem requires to find the maximum possible score that can be obtained by applying at most k operations on an array of positive integers
• The operations involve choosing a non-empty subarray with the highest prime score and multiplying the score by the chosen element.

Approach

• The solution uses the Sieve of Eratosthenes to generate prime numbers up to the maximum element in the array
• It then calculates the prime score for each number in the array and uses a stack to find the dominant indices for each number
• The maximum possible score is then calculated by raising the element with the maximum value to the power of the number of operations available.

Complexity

• O(n log n) due to the Sieve of Eratosthenes and O(n log n) due to the sorting of the array
• The power function has a complexity of O(log n) and the overall complexity is dominated by the sorting and Sieve of Eratosthenes steps.

Solution Code:

class Solution {
public:
    const int MOD = 1e9 + 7;

    int maximumScore(vector& nums, int k) {
        int n = nums.size();
        vector primeScores(n, 0);

        // Find the maximum element in nums to determine the range for prime
        // generation
        int maxElement = 0;
        for (int index = 0; index < n; index++) {
            maxElement = max(maxElement, nums[index]);
        }

        // Get all prime numbers up to maxElement using the Sieve of
        // Eratosthenes
        vector primes = getPrimes(maxElement);

        // Calculate the prime score for each number in nums
        for (int index = 0; index < n; index++) {
            int num = nums[index];

            // Iterate over the generated primes to count unique prime factors
            for (int prime : primes) {
                if (prime * prime > num)
                    break;  // Stop early if prime^2 exceeds num
                if (num % prime != 0)
                    continue;  // Skip if the prime is not a factor

                primeScores[index]++;  // Increment prime score for the factor
                while (num % prime == 0)
                    num /= prime;  // Remove all occurrences of this factor
            }

            // If num is still greater than 1, it is a prime number itself
            if (num > 1) primeScores[index]++;
        }

        // Initialize next and previous dominant index arrays
        vector nextDominant(n, n);
        vector prevDominant(n, -1);

        // Stack to store indices for a monotonic decreasing prime score
        stack decreasingPrimeScoreStack;

        // Calculate the next and previous dominant indices for each number
        for (int index = 0; index < n; index++) {
            // While the stack is not empty and the current prime score is
            // greater than the stack's top, update nextDominant
            while (!decreasingPrimeScoreStack.empty() &&
                   primeScores[decreasingPrimeScoreStack.top()] <
                       primeScores[index]) {
                int topIndex = decreasingPrimeScoreStack.top();
                decreasingPrimeScoreStack.pop();

                // Set the next dominant element for the popped index
                nextDominant[topIndex] = index;
            }

            // If the stack is not empty, set the previous dominant element for
            // the current index
            if (!decreasingPrimeScoreStack.empty())
                prevDominant[index] = decreasingPrimeScoreStack.top();

            // Push the current index onto the stack
            decreasingPrimeScoreStack.push(index);
        }

        // Calculate the number of subarrays in which each element is dominant
        vector numOfSubarrays(n);
        for (int index = 0; index < n; index++) {
            numOfSubarrays[index] = (long long)(nextDominant[index] - index) *
                                    (index - prevDominant[index]);
        }

        // Sort elements in decreasing order based on their values
        vector> sortedArray(n);
        for (int index = 0; index < n; index++) {
            sortedArray[index] = {nums[index], index};
        }

        sort(sortedArray.begin(), sortedArray.end(), greater<>());

        long long score = 1;
        int processingIndex = 0;

        // Process elements while there are operations left
        while (k > 0) {
            // Get the element with the maximum value
            auto [num, index] = sortedArray[processingIndex++];

            // Calculate the number of operations to apply on the current
            // element
            long long operations = min((long long)k, numOfSubarrays[index]);

            // Update the score by raising the element to the power of
            // operations
            score = (score * power(num, operations)) % MOD;

            // Reduce the remaining operations count
            k -= operations;
        }

        return score;
    }

private:
    // Helper function to compute the power of a number modulo MOD
    long long power(long long base, long long exponent) {
        long long res = 1;

        // Calculate the exponentiation using binary exponentiation
        while (exponent > 0) {
            // If the exponent is odd, multiply the result by the base
            if (exponent % 2 == 1) {
                res = ((res * base) % MOD);
            }

            // Square the base and halve the exponent
            base = (base * base) % MOD;
            exponent /= 2;
        }

        return res;
    }

    // Function to generate prime numbers up to a given limit using the Sieve of
    // Eratosthenes
    vector getPrimes(int limit) {
        vector isPrime(limit + 1, true);
        vector primes;

        // Start marking from the first prime number (2)
        for (int number = 2; number <= limit; number++) {
            if (!isPrime[number]) continue;

            // Store the prime number
            primes.push_back(number);

            // Mark multiples of the prime number as non-prime
            for (long long multiple = (long long)number * number;
                 multiple <= limit; multiple += number) {
                isPrime[multiple] = false;
            }
        }

        return primes;
    }
};

Leetcode Problem:

• Maximum Number of Points From Grid Queries

Summary

• Finding Maximum Points in a Grid Based on Queries

Approach

• This solution uses a priority queue to keep track of the cells in the grid that need to be visited
• The priority queue is implemented using a binary heap
• The solution starts from the top left cell and keeps track of the maximum points that can be obtained for each query
• The time complexity is O(m*n*log(m*n)), where m and n are the dimensions of the grid.

Complexity

• O(m*n*log(m*n))

Explanation

• The solution first initializes a visited matrix to keep track of the cells that have been visited
• It also initializes a priority queue with the top left cell of the grid
• Then, it enters a loop where it pops the cell with the maximum value from the priority queue and marks it as visited
• For each cell, it checks all its adjacent cells and pushes them into the priority queue if they have not been visited before
• Finally, it calculates the maximum points that can be obtained for each query by summing up the points obtained for each cell in the priority queue.

Solution Code:

struct _node{
    int r;
    int c;
    int v;
};

template 
struct _heap{
    T arr[1000001];
    int size;
    _heap(){
        size = 1;
    }
    void push(T a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && arr[idx/2].v > arr[idx].v){
            T t = arr[idx/2];
            arr[idx/2] = arr[idx];
            arr[idx] = t;
            idx /= 2;
        }
    }
    T pop(){
        T 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].v > arr[j+1].v){
                j++;
            }
            if(arr[i].v > arr[j].v){
                T t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else{
                break;
            }
        }
        return ret;
    }
    bool empty(){
        return size == 1;
    }
};

class Solution {
public:
    _heap<_node> h;
    bool visited[1001][1001];
    int answer[1000001] = {0};
    vector maxPoints(vector>& grid, vector& queries) {
        vector ans;
        int cur_query = 0;
        int dy[] = {0, 1, 0, -1};
        int dx[] = {1, 0, -1, 0};

        visited[0][0] = true;
        h.push({0, 0, grid[0][0]});
        
        while(!h.empty()){
            _node nod = h.pop();
            cur_query = max(cur_query, nod.v);
            answer[cur_query]++;
            for(int i = 0 ; i < 4; i++){
                int nr = nod.r + dy[i];
                int nc = nod.c + dx[i];
                if(nr < 0 || nr >= grid.size() || nc < 0 || nc >= grid[0].size() || visited[nr][nc]){
                    continue;
                }
                visited[nr][nc] = true;
                h.push({nr, nc, grid[nr][nc]});
            }
        }
        for(int i = 1 ; i < 1000001; i++){
            answer[i] = answer[i-1] + answer[i];
        }
        for(int i = 0 ; i < queries.size(); i++){
            ans.push_back(answer[queries[i]-1]);
        }
        return ans;
    }
};

Leetcode Problem:

• Minimum Index of a Valid Split

Summary

• Finding the minimum index of a valid split in an array where more than half of the elements have the same value.

Approach

• The approach used is to iterate over the array and maintain two maps, left and right, to store the count of each number
• We then iterate over the array again, pushing the current number to the right map and popping it from the left map
• If the count of the current number in both maps is more than half of the remaining elements, we return the current index
• If no valid split is found, we return -1.

Complexity

• O(n log n) due to the use of maps and the nested loop structure

Explanation

• The solution uses two maps, left and right, to store the count of each number in the array
• We iterate over the array twice, once to populate the maps and once to find the valid split
• In the first iteration, we push the current number to the right map and pop it from the left map
• In the second iteration, we check if the count of the current number in both maps is more than half of the remaining elements
• If it is, we return the current index
• If not, we continue to the next iteration
• If no valid split is found, we return -1.

Solution Code:

struct _node{
    int num;
    int cnt;
};

struct _map{
    vector<_node> m[10000];
    void push(int num){
        int idx = num % 10000;
        for(int i = 0 ; i < m[idx].size(); i++){
            if(m[idx][i].num == num){
                m[idx][i].cnt++;
                return;
            }
        }
        m[idx].push_back({num, 1});
    }
    int getCnt(int num){
        int idx = num % 10000;
        for(int i = 0 ; i < m[idx].size(); i++){
            if(m[idx][i].num == num){
                return m[idx][i].cnt;
            }
        }
        return -1;
    }
    void pop(int num){
        int idx = num% 10000;
        for(int i = 0 ; i < m[idx].size(); i++){
            if(m[idx][i].num == num){
                m[idx][i].cnt--;
                if(m[idx][i].cnt == 0){
                    m[idx][i] = m[idx][m[idx].size() - 1];
                    m[idx].pop_back();
                }
            }
        }
    }
};

class Solution {
public:
    _map left;
    _map right;
    int minimumIndex(vector& nums) {
        for(int i = 0 ; i < nums.size(); i++){
            right.push(nums[nums.size() - i - 1]);
        }
        for(int i = 0 ; i < nums.size(); i++){
            left.push(nums[i]);
            right.pop(nums[i]);
            int n = left.getCnt(nums[i]);
            if(n * 2 <= (i + 1)){
                continue;
            }
            n = right.getCnt(nums[i]);
            if(n == -1) continue;
            if((n * 2) > (nums.size() - i - 1)){
                return i;
            }
        }
        return -1;
    }
};

Leetcode Problem:

• Minimum Operations to Make a Uni-Value Grid

Summary

• This problem requires finding the minimum number of operations to make a 2D grid uni-value by adding or subtracting a given number x from any element in the grid.

Approach

• The solution first finds the minimum value in the grid and then calculates the sum of all elements in the grid after subtracting the minimum value
• It then checks if the sum is divisible by x and if it is, it calculates the minimum number of operations needed to make all elements equal to the sum divided by the number of elements in the grid
• If the sum is not divisible by x, it returns -1
• Otherwise, it uses a binary search approach to find the minimum number of operations needed to make all elements equal to the sum divided by the number of elements in the grid.

Complexity

• O(m*n log(m*n))

Explanation

• The solution first finds the minimum value in the grid and then calculates the sum of all elements in the grid after subtracting the minimum value
• It then checks if the sum is divisible by x and if it is, it calculates the minimum number of operations needed to make all elements equal to the sum divided by the number of elements in the grid
• If the sum is not divisible by x, it returns -1
• Otherwise, it uses a binary search approach to find the minimum number of operations needed to make all elements equal to the sum divided by the number of elements in the grid.

Solution Code:

class Solution {
public:
    int minOperations(vector>& grid, int x) {
        int m = grid.size();
        int n = grid[0].size();
        int minValue = 1000000;
        for(int i = 0 ; i < m; i++){
            for(int j = 0 ; j < n; j++){
                if(minValue > grid[i][j]){
                    minValue = grid[i][j];
                }
            }
        }
        int sum = 0;        
        for(int i = 0 ; i < m; i++){
            for(int j = 0 ; j < n; j++){
                grid[i][j] -= minValue;
                if(grid[i][j] % x != 0) return -1;
                grid[i][j] /= x;
                sum += grid[i][j];
            }
        }
        double temp = sum / double(m*n);
        int goal = temp + 0.5;
        int ans = 1000000001;
        for(int k = -20; k <= 20; k++){
            int goal2 = goal + k;
            int sum2 = 0;
            for(int i = 0 ; i < m; i++){
                for(int j = 0 ; j < n; j++){
                    sum2 += abs(goal2 - grid[i][j]);
                }
            }
            ans = min(ans, sum2);
        }
        
        return ans;
    }
};

Leetcode Problem:

• Check if Grid can be Cut into Sections

Summary

• Problem: Determine if it is possible to make two horizontal or two vertical cuts on an n x n grid such that each cut contains at least one rectangle and every rectangle belongs to exactly one section.

Approach

• The solution uses a two-dimensional approach, trying both horizontal and vertical cuts
• It sorts the rectangles by their starting coordinate in the given dimension and tracks the furthest ending coordinate seen so far
• It then checks for gaps between rectangles where a cut can be made
• The solution returns true if at least two gaps are found, indicating that valid cuts can be made.

Complexity

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

Explanation

• The solution first tries both horizontal and vertical cuts using the `checkCuts` function, which takes a 2D array of rectangles and a dimension (0 for horizontal cuts and 1 for vertical cuts) as input
• The `checkCuts` function sorts the rectangles by their starting coordinate in the given dimension and tracks the furthest ending coordinate seen so far
• It then checks for gaps between rectangles where a cut can be made
• The function returns true if at least two gaps are found, indicating that valid cuts can be made.

Solution Code:

class Solution {
public:
    bool checkValidCuts(int n, vector>& rectangles) {
        // Try both horizontal and vertical cuts
        return checkCuts(rectangles, 0) || checkCuts(rectangles, 1);
    }

private:
    // Check if valid cuts can be made in a specific dimension
    bool checkCuts(vector>& rectangles, int dim) {
        int gapCount = 0;

        // Sort rectangles by their starting coordinate in the given dimension
        sort(rectangles.begin(), rectangles.end(),
             [dim](const vector& a, const vector& b) {
                 return a[dim] < b[dim];
             });

        // Track the furthest ending coordinate seen so far
        int furthestEnd = rectangles[0][dim + 2];

        for (size_t i = 1; i < rectangles.size(); i++) {
            vector& rect = rectangles[i];

            // If current rectangle starts after the furthest end we've seen,
            // we found a gap where a cut can be made
            if (furthestEnd <= rect[dim]) {
                gapCount++;
            }

            // Update the furthest ending coordinate
            furthestEnd = max(furthestEnd, rect[dim + 2]);
        }

        // We need at least 2 gaps to create 3 sections
        return gapCount >= 2;
    }
};

Leetcode Problem:

• Count Days Without Meetings

Summary

• Given a positive integer days representing the total number of days an employee is available for work, and a 2D array meetings of size n where, meetings[i] = [start_i, end_i] represents the starting and ending days of meeting i (inclusive), return the count of days when the employee is available for work but no meetings are scheduled.

Approach

• The approach used is to first sort the meetings array, then initialize two pointers l and r to the start and end of the first meeting respectively
• Then, iterate over the rest of the meetings and update the end of the last meeting that ends earliest
• Finally, add the available days before the first meeting and after the last meeting to the answer.

Complexity

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

Solution Code:

class Solution {
public:
    int countDays(int days, vector>& meetings) {
        sort(meetings.begin(), meetings.end());
        int l = meetings[0][0];
        int r = meetings[0][1];
        int ans = 0;
        ans += l - 1;
        for(int i = 1 ; i < meetings.size(); i++){
            int ll = meetings[i][0];
            int rr = meetings[i][1];
            cout << ll << " " << rr << endl;
            if(r < ll){
                ans += ll - r - 1;
            }
            r = max(r, rr);
        }
        ans += days - r;
        return ans;
    }
};

Leetcode Problem:

• Count the Number of Complete Components

Summary

• This is a problem about finding the number of complete connected components in a graph.

Approach

• The approach used in the solution code is to use a disjoint set data structure to keep track of the connected components in the graph
• The code first initializes the disjoint set data structure and then iterates over the edges in the graph
• For each edge, it checks if the two vertices are in the same connected component
• If they are not, it merges the two components by attaching the root of one component to the root of the other component
• The code also keeps track of the number of edges in each component
• Finally, it checks each component to see if it is complete by checking if the number of edges in the component is equal to the number of ways to choose two vertices from the component (i.e., n*(n-1)/2)
• If a component is not complete, it is removed from the set of components
• The final answer is the number of complete components remaining in the set.

Complexity

• O(n*m*log(n)) where n is the number of vertices and m is the number of edges in the graph.

Explanation

• The code first initializes the disjoint set data structure and the edge count array
• It then iterates over the edges in the graph and checks if the two vertices are in the same connected component
• If they are not, it merges the two components by attaching the root of one component to the root of the other component
• The code also keeps track of the number of edges in each component
• Finally, it checks each component to see if it is complete by checking if the number of edges in the component is equal to the number of ways to choose two vertices from the component (i.e., n*(n-1)/2)
• If a component is not complete, it is removed from the set of components
• The final answer is the number of complete components remaining in the set.

Solution Code:

class Solution {
public:
    int uf[51];
    int edgeCnt[51] = {0};
    int groupCnt[51] = {0};
    int disjointSet(int x){
        if (x == uf[x]) return x;
        return uf[x] = disjointSet(uf[x]);
    }
    int countCompleteComponents(int n, vector>& edges) {
        if (n == 1) return 1;
        set ans;
        for(int i = 0 ; i < n; i++){
            uf[i] = i;
            groupCnt[i] = 1;
        }
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            if(disjointSet(a) != disjointSet(b)){
                groupCnt[disjointSet(b)] += groupCnt[disjointSet(a)];
                groupCnt[disjointSet(a)] = 0;
                edgeCnt[disjointSet(b)] += edgeCnt[disjointSet(a)];
                edgeCnt[disjointSet(b)] += 1;
                edgeCnt[disjointSet(a)] = 0;
                uf[disjointSet(a)] = disjointSet(b);
            }else{
                edgeCnt[disjointSet(b)] += 1;
            }
        }
        for(int i = 0 ; i < n; i++){
            if(ans.find(disjointSet(i)) == ans.end()){
                ans.insert(disjointSet(i));
            }
        }
        cout << "answer size: " << ans.size() << endl;
        vector removeList;
        for(auto idx : ans){
            int n = groupCnt[disjointSet(idx)];
            int e = edgeCnt[disjointSet(idx)];
            cout << n << " " << e << endl;
            if((n*(n-1)/2) != e){
                removeList.push_back(idx);
            }
        }
        for(int i = 0 ; i < removeList.size(); i++){
            ans.erase(removeList[i]);
        }
        return ans.size();
    }
};