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

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

Leetcode Problem:

• Find All Possible Recipes from Given Supplies

Summary

• Find all the recipes that can be created with the given ingredients and supplies.

Approach

• Breadth-First Search (BFS) algorithm is used to traverse the graph of recipes and ingredients
• The algorithm starts by initializing a queue with all the recipes and a set of available supplies
• Then, it iteratively pops a recipe from the queue, checks if all its ingredients are available, and if so, adds it to the set of available supplies and the result list
• If not, it pushes the recipe back into the queue to be processed later.

Complexity

• O(N + M) where N is the number of recipes and M is the total number of ingredients

Explanation

• The algorithm uses a queue to keep track of the recipes to be processed and a set to keep track of the available supplies
• It iterates over the recipes and checks if all their ingredients are available
• If they are, it adds the recipe to the set of available supplies and the result list
• If not, it pushes the recipe back into the queue to be processed later
• This process continues until all recipes have been processed or the queue is empty.

Solution Code:

class Solution {
public:
    queue que;
    set supply;
    vector findAllRecipes(vector& recipes, vector>& ingredients, vector& supplies) {
        int N = recipes.size();
        
        for(int i = 0 ; i < N; i++){
            que.push(i);
        }
        for(int i = 0 ; i < supplies.size(); i++){
            supply.insert(supplies[i]);
        }
        vector ans;
        int cnt = 0;
        while(!que.empty() && cnt < N){
            int idx = que.front();
            que.pop();
            bool success = true;
            for(int i = 0; i < ingredients[idx].size(); i++){
                if(supply.find(ingredients[idx][i]) == supply.end()){
                    success = false;
                    break;
                }
            }
            if(success){
                supply.insert(recipes[idx]);
                ans.push_back(recipes[idx]);
                cnt = -1;
                N--;
            } else{
                que.push(idx);
            }
            cnt++;
        }
        return ans;
    }
};

Leetcode Problem:

• Minimum Cost Walk in Weighted Graph

Summary

• Find the minimum cost of a walk between two nodes in an undirected weighted graph.

Approach

• Disjoint Set Union (DSU) algorithm is used to find the minimum cost of a walk between two nodes in an undirected weighted graph
• The DSU algorithm is used to find the set that each node belongs to and the minimum cost of the walk is calculated by performing a bitwise AND operation on the weights of the edges in the same set.

Complexity

• O(n + m log n), where n is the number of nodes and m is the number of edges.

Explanation

• The solution code first initializes the DSU array and the groupWeight array
• Then it iterates over the edges and updates the groupWeight array by performing a bitwise AND operation on the weights of the edges in the same set
• Finally, it iterates over the queries and calculates the minimum cost of the walk for each query by performing a bitwise AND operation on the weights of the edges in the same set.

Solution Code:

class Solution {
public:
    int uf[100001];
    int groupWeight[100001];
    int disjointSet(int x){
        if(x == uf[x]) return x;
        return uf[x] = disjointSet(uf[x]);
    }
    vector minimumCost(int n, vector>& edges, vector>& query) {
        for(int i = 0 ; i < n ;i++){
            uf[i] = i;
            groupWeight[i] = 0x0FFFFFFF;
        }
        for(int i = 0; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            int w = edges[i][2];
            int ww = groupWeight[disjointSet(a)] & groupWeight[disjointSet(b)] & w;
            uf[disjointSet(a)] = disjointSet(b);
            groupWeight[disjointSet(a)] = ww;
        }
        vector ans;
        for(int i = 0 ; i < query.size(); i++){
            int s = query[i][0];
            int e = query[i][1];
            if(disjointSet(s) == disjointSet(e)){
                ans.push_back(groupWeight[disjointSet(s)]);
            }else{
                ans.push_back(-1);
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Minimum Operations to Make Binary Array Elements Equal to One I

Summary

• Given a binary array, find the minimum number of operations to make all elements equal to 1 by flipping 3 consecutive elements at a time.

Approach

• The approach is to iterate through the array and flip 3 consecutive elements at a time until no more flips are possible
• If a 3 consecutive elements cannot be found, return -1.

Complexity

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

Explanation

• The solution iterates through the array and checks if the current element and the next two elements are 0
• If they are, it flips them and increments the answer
• This process continues until no more flips are possible
• If at any point a 3 consecutive elements cannot be found, the function returns -1.

Solution Code:

class Solution {
public:
    int minOperations(vector& nums) {
        int ans = 0;
        for(int i = 0 ; i < nums.size(); i++){
            if(nums[i] == 0){
                for(int j = i; j < i + 3; j++){
                    if(j >= nums.size()) return -1;
                    nums[j] ^= 1;
                }
                ans++;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Split Linked List in Parts

Summary

• Given a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

Approach

• The approach used is to first store the values of the linked list in a vector
• Then, for each part, create a new linked list with the required number of nodes
• The remaining nodes are then added to the next part.

Complexity

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

Explanation

• The solution starts by storing the values of the linked list in a vector
• This is done to easily access the values of the linked list
• Then, for each part, a new linked list is created with the required number of nodes
• The remaining nodes are then added to the next part
• This process is repeated for each part, until all parts have been created
• The time complexity of the solution is O(n), where n is the number of nodes in the linked list, because each node is visited once
• The space complexity is also O(n), because in the worst case, all nodes are stored in the vector.

Solution Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector splitListToParts(ListNode* head, int k) {
        ListNode* ptr = head;
        vector arr;
        vector ans;
        while(ptr){
            arr.push_back(ptr->val);
            ptr = ptr->next;
        }
        int N = arr.size();
        int more = arr.size() % k;
        int arrIdx = 0;
        for(int i = 0 ; i < k ; i++){
            ListNode* tmp = nullptr;
            ListNode* ptr;
            for(int j = 0; j < N / k; j++){
                if (tmp == nullptr) {
                    tmp = new ListNode(arr[arrIdx++]);
                    ptr = tmp;
                } else{
                    ptr->next = new ListNode(arr[arrIdx++]);
                    ptr = ptr->next;
                }
            }
            if (more){
                if (tmp == nullptr) {
                    tmp = new ListNode(arr[arrIdx++]);
                    ptr = tmp;
                } else{
                    ptr->next = new ListNode(arr[arrIdx++]);
                    ptr = ptr->next;
                }
                more--;
            }
            ans.push_back(tmp);
        }

        return ans;
    }
};