짬뽕얼큰하게의 맨땅에 헤딩 :: '알고리즘' 카테고리의 글 목록 (2 Page)

Count the Number of Complete Components

알고리즘 2025. 3. 22. 23:44

Leetcode Problem:

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

'알고리즘' 카테고리의 다른 글

Check if Grid can be Cut into Sections  (0) 2025.03.25
Count Days Without Meetings  (0) 2025.03.24
Find All Possible Recipes from Given Supplies  (0) 2025.03.21
Minimum Cost Walk in Weighted Graph  (0) 2025.03.20
Minimum Operations to Make Binary Array Elements Equal to One I  (0) 2025.03.19
블로그 이미지

짬뽕얼큰하게

,

Find All Possible Recipes from Given Supplies

알고리즘 2025. 3. 21. 22:27

Leetcode Problem:

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

'알고리즘' 카테고리의 다른 글

Count Days Without Meetings  (0) 2025.03.24
Count the Number of Complete Components  (0) 2025.03.22
Minimum Cost Walk in Weighted Graph  (0) 2025.03.20
Minimum Operations to Make Binary Array Elements Equal to One I  (0) 2025.03.19
Split Linked List in Parts  (0) 2025.03.19
블로그 이미지

짬뽕얼큰하게

,

Minimum Cost Walk in Weighted Graph

알고리즘 2025. 3. 20. 22:10

Leetcode Problem:

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

'알고리즘' 카테고리의 다른 글

Count the Number of Complete Components  (0) 2025.03.22
Find All Possible Recipes from Given Supplies  (0) 2025.03.21
Minimum Operations to Make Binary Array Elements Equal to One I  (0) 2025.03.19
Split Linked List in Parts  (0) 2025.03.19
Longest Nice Subarray  (0) 2025.03.18
블로그 이미지

짬뽕얼큰하게

,

Minimum Operations to Make Binary Array Elements Equal to One I

알고리즘 2025. 3. 19. 23:20

Leetcode Problem:

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

'알고리즘' 카테고리의 다른 글

Find All Possible Recipes from Given Supplies  (0) 2025.03.21
Minimum Cost Walk in Weighted Graph  (0) 2025.03.20
Split Linked List in Parts  (0) 2025.03.19
Longest Nice Subarray  (0) 2025.03.18
Divide Array Into Equal Pairs  (0) 2025.03.17
블로그 이미지

짬뽕얼큰하게

,

Split Linked List in Parts

알고리즘 2025. 3. 19. 08:37

Leetcode Problem:

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

'알고리즘' 카테고리의 다른 글

Minimum Cost Walk in Weighted Graph  (0) 2025.03.20
Minimum Operations to Make Binary Array Elements Equal to One I  (0) 2025.03.19
Longest Nice Subarray  (0) 2025.03.18
Divide Array Into Equal Pairs  (0) 2025.03.17
Minimum Time to Repair Cars  (0) 2025.03.16
블로그 이미지

짬뽕얼큰하게

,

Longest Nice Subarray

알고리즘 2025. 3. 18. 21:42

Leetcode Problem:

Summary

  • The problem is to find the length of the longest nice subarray in a given array of positive integers.

Approach

  • The approach used is to use a sliding window technique, where we keep expanding the window to the right as long as the bitwise AND of the current prefix sum and the next element is 0
  • If the condition is not met, we shrink the window from the left.

Complexity

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

Explanation

  • The solution code initializes two pointers, l and r, to the start of the array
  • It also initializes a variable, prefixSum, to keep track of the bitwise AND of the current prefix sum and the next element
  • The code then enters a loop where it checks if the bitwise AND of the current prefix sum and the next element is 0
  • If it is, the code adds the next element to the prefix sum and moves the right pointer to the right
  • If it is not, the code subtracts the leftmost element from the prefix sum and moves the left pointer to the right
  • The code keeps track of the maximum length of the nice subarray and returns it at the end.

Solution Code:


class Solution {
public:
    int longestNiceSubarray(vector& nums) {
        int l = 0;
        int r = 0;
        int prefixSum = 0;
        int ans = 0;
        while(l < nums.size() && r < nums.size()){
            if((prefixSum & nums[r]) == 0){
                prefixSum += nums[r];
                r++;
                ans = max(ans, r - l);
            }else{
                prefixSum -= nums[l];
                l++;
            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Minimum Operations to Make Binary Array Elements Equal to One I  (0) 2025.03.19
Split Linked List in Parts  (0) 2025.03.19
Divide Array Into Equal Pairs  (0) 2025.03.17
Minimum Time to Repair Cars  (0) 2025.03.16
House Robber IV  (0) 2025.03.15
블로그 이미지

짬뽕얼큰하게

,

Divide Array Into Equal Pairs

알고리즘 2025. 3. 17. 23:06

Leetcode Problem:

Summary

  • Check if an array of integers can be divided into pairs of equal numbers.

Approach

  • Count the occurrences of each number in the array and check if all counts are even
  • If any count is odd, return false
  • Otherwise, return true.

Complexity

  • O(n) where n is the length of the input array

Explanation

  • The solution first counts the occurrences of each number in the array using an array cnt
  • Then, it checks if all counts are even by iterating from 1 to 500
  • If any count is odd, it returns false
  • Otherwise, it returns true.

Solution Code:


class Solution {
public:
    int cnt[501] = {0};
    bool divideArray(vector& nums) {
        for(int n : nums){
            cnt[n]++;
        }
        for(int i = 1; i <= 500; i++){
            if(cnt[i] &1){
                return false;
            }
        }
        return true;
    }
};

'알고리즘' 카테고리의 다른 글

Split Linked List in Parts  (0) 2025.03.19
Longest Nice Subarray  (0) 2025.03.18
Minimum Time to Repair Cars  (0) 2025.03.16
House Robber IV  (0) 2025.03.15
Zero Array Transformation II  (0) 2025.03.14
블로그 이미지

짬뽕얼큰하게

,

Minimum Time to Repair Cars

알고리즘 2025. 3. 16. 09:48

Leetcode Problem:

Summary

  • Find the minimum time to repair all cars given the ranks of mechanics and the total number of cars.

Approach

  • Binary Search: The solution uses binary search to find the minimum time to repair all cars
  • It initializes two pointers, l and r, to the minimum and maximum possible times
  • It then calculates the midpoint and checks if the number of cars that can be repaired within the time limit is less than or equal to the total number of cars
  • If it is, it updates the minimum time and moves the left pointer to the right
  • Otherwise, it updates the maximum time and moves the right pointer to the left
  • This process continues until the two pointers meet, and the minimum time is returned.

Complexity

  • O(n log m) where n is the number of mechanics and m is the maximum rank

Explanation

  • The solution first initializes two pointers, l and r, to the minimum and maximum possible times
  • It then calculates the midpoint and checks if the number of cars that can be repaired within the time limit is less than or equal to the total number of cars
  • If it is, it updates the minimum time and moves the left pointer to the right
  • Otherwise, it updates the maximum time and moves the right pointer to the left
  • This process continues until the two pointers meet, and the minimum time is returned
  • The time complexity is O(n log m) because the solution uses binary search, which has a time complexity of O(log m), and it needs to iterate over the mechanics, which takes O(n) time.

Solution Code:


class Solution {
public:
    long long repairCars(vector& ranks, int cars) {
        long long l = 0;
        long long r = 100000000000000;
        long long ans = 0;
        while(l <= r){
            long long mid = (l + r ) / 2;
            long long repairCar = 0;
            for(int i = 0 ; i < ranks.size(); i++){
                long long tmp = mid/ranks[i];
                repairCar += sqrt(tmp);
            }
            if(repairCar < cars){
                l = mid + 1;
            } else{
                ans = mid;
                r = mid - 1;
            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Longest Nice Subarray  (0) 2025.03.18
Divide Array Into Equal Pairs  (0) 2025.03.17
House Robber IV  (0) 2025.03.15
Zero Array Transformation II  (0) 2025.03.14
Maximum Count of Positive Integer and Negative Integer  (0) 2025.03.13
블로그 이미지

짬뽕얼큰하게

,

House Robber IV

알고리즘 2025. 3. 15. 23:39

Leetcode Problem:

Summary

  • The problem is to find the minimum capability of a robber to steal money from houses along a street, given the amount of money in each house and the minimum number of houses the robber will steal from.

Approach

  • Binary Search Approach: The solution uses a binary search approach to find the minimum capability of the robber
  • It initializes two pointers, `l` and `r`, to represent the minimum and maximum possible capability
  • It then iterates through the range of possible capabilities, checking if the number of houses that can be robbed is greater than or equal to `k`
  • If it is, it updates the maximum capability to the current value and moves the right pointer to the left
  • Otherwise, it moves the left pointer to the right.

Complexity

  • O(n log m) where n is the number of houses and m is the maximum possible capability

Explanation

  • The solution starts by initializing two pointers, `l` and `r`, to represent the minimum and maximum possible capability
  • It then iterates through the range of possible capabilities using a binary search approach
  • For each capability `mid`, it counts the number of houses that can be robbed and checks if it is greater than or equal to `k`
  • If it is, it updates the maximum capability to the current value and moves the right pointer to the left
  • Otherwise, it moves the left pointer to the right
  • The solution continues until `l` is greater than `r`, at which point it returns the maximum capability as the minimum capability of the robber.

Solution Code:


class Solution {
public:
    int minCapability(vector& nums, int k) {
        int l = 1;
        int r = 1000000000;
        int ans = 0;
        while(l <= r){
            // int mid = l + ((r - l) >> 1);
            int mid = (l + r)/2;
            int cnt = 0;
            for(int i = 0 ; i < nums.size(); i++){
                if(nums[i] <= mid){
                    cnt++;
                    i++;
                }
            }
            if(cnt >= k){
                r = mid - 1;
                ans = mid;
            } else{
                l = mid + 1;

            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Divide Array Into Equal Pairs  (0) 2025.03.17
Minimum Time to Repair Cars  (0) 2025.03.16
Zero Array Transformation II  (0) 2025.03.14
Maximum Count of Positive Integer and Negative Integer  (0) 2025.03.13
Number of Substrings Containing All Three Characters  (0) 2025.03.11
블로그 이미지

짬뽕얼큰하게

,

Zero Array Transformation II

알고리즘 2025. 3. 14. 08:38

Leetcode Problem:

Summary

  • Given an integer array and a 2D array of queries, find the minimum possible non-negative value of k such that after processing the first k queries in sequence, the array becomes a Zero Array.

Approach

  • This problem can be solved by using binary search to find the minimum possible value of k
  • We start by initializing two pointers, l and r, to the start and end of the queries array respectively
  • We then calculate the sum of the values to be decremented for each query and update the offset array accordingly
  • If the array becomes a Zero Array after processing the current query, we update the answer and move the right pointer to the left
  • If not, we move the left pointer to the right
  • We repeat this process until we find the minimum possible value of k or until l is greater than r.

Complexity

  • O(n log q) where n is the size of the nums array and q is the size of the queries array

Explanation

  • The time complexity of this solution is O(n log q) because we are using binary search to find the minimum possible value of k
  • In the worst case, we need to process each query in the queries array, which takes O(n) time
  • We repeat this process log q times, where log q is the number of iterations of the binary search
  • The space complexity is O(n) because we need to store the offset array, which has n elements.

Solution Code:


class Solution {
public:
    int offset[100002];
    int minZeroArray(vector& nums, vector>& queries) {
        int l = 0;
        int r = queries.size();
        int ans = 100001;
        while(l <= r){
            int mid = (l + r) / 2;
            for(int i = 0 ; i < nums.size(); i++){
                offset[i] = 0;
            }
            for(int i = 0; i < mid; i++){
                offset[queries[i][0]] += queries[i][2];
                offset[queries[i][1] + 1] -= queries[i][2];
            }
            for(int i = 1; i < nums.size(); i++){
                offset[i] += offset[i-1];
            }
            bool success = true;
            for(int i = 0 ; i < nums.size() ;i++){
                if((nums[i] - offset[i]) > 0){
                    success = false;
                    break;
                }
            }
            if(success){
                ans = mid;
                r = mid - 1;
            } else{
                l = mid + 1;
            }
        }
        if( ans == 100001) return -1;
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Minimum Time to Repair Cars  (0) 2025.03.16
House Robber IV  (0) 2025.03.15
Maximum Count of Positive Integer and Negative Integer  (0) 2025.03.13
Number of Substrings Containing All Three Characters  (0) 2025.03.11
Count of Substrings Containing Every Vowel and K Consonants II  (0) 2025.03.10
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/04   »
일 월 화 수 목 금 토
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30

티스토리툴바