짬뽕얼큰하게의 맨땅에 헤딩 :: '2025/02 글 목록 (17 Page)

Average Waiting Time

알고리즘 2025. 2. 2. 20:53

summary

  • Calculate the average waiting time of customers in a restaurant.

approach

  • This solution uses a greedy approach to calculate the average waiting time of customers
  • It iterates over the customers and calculates the waiting time for each customer based on the time the chef is idle
  • The total waiting time is then divided by the number of customers to get the average waiting time.

complexity

  • O(n)

explain

  • The solution works by iterating over the customers and calculating the waiting time for each customer
  • If the customer arrives after the chef is idle, the waiting time is the time the chef has been idle plus the preparation time
  • If the customer arrives before the chef is idle, the waiting time is the time the chef has been idle plus the preparation time minus the time the customer arrived
  • The total waiting time is then divided by the number of customers to get the average waiting time.

Solution Code:


class Solution {
public:
    double averageWaitingTime(vector>& customers) {
        long long totalWait = 0;
        long long time = 0;
        for(int i = 0 ; i < customers.size(); i++){
            int arrival = customers[i][0];
            int prepareTime = customers[i][1];

            if (arrival > time){
                time = arrival + prepareTime;
                totalWait += prepareTime;
            } else {
                totalWait += time - arrival + prepareTime;
                time += prepareTime;
            }
        }
        return (double)totalWait / customers.size();
    }
};

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

Reverse Substrings Between Each Pair of Parentheses  (0) 2025.02.02
Crawler Log Folder  (0) 2025.02.02
Find the Winner of the Circular Game  (0) 2025.02.02
Water Bottles  (0) 2025.02.02
Pass the Pillow  (0) 2025.02.02
블로그 이미지

짬뽕얼큰하게

,

Find the Winner of the Circular Game

알고리즘 2025. 2. 2. 20:50

summary

  • The problem is a game where n friends are sitting in a circle and the winner is determined by counting k friends in the clockwise direction, including the starting friend
  • The last friend counted leaves the circle and loses the game.

approach

  • The approach used in the solution code is to simulate the game by inserting the friends into a circular linked list and then repeatedly removing the last k friends from the list until only one friend is left
  • The last remaining friend is the winner.

complexity

  • The time complexity of the solution code is O(n * k), where n is the number of friends and k is the number of friends to count
  • This is because the code inserts each friend into the list once and then repeatedly removes the last k friends from the list until only one friend is left.

explain

  • The solution code first inserts all n friends into a circular linked list using the `insertLast` method
  • Then, it repeatedly removes the last k friends from the list using the `removeK` method until only one friend is left
  • The last remaining friend is the winner, which is returned by the `findTheWinner` method.

Solution Code:


struct node{
    int val;
    struct node *next;
    struct node *prev;
    node(){
        val = -1;
        next = this;
        prev = this;
    }
};




class Solution {
public:
    node head;
    
    void insertLast(int v){
        node* newNode = new node();
        newNode->val = v;
        newNode->prev = head.prev;
        newNode->next = &head;
        head.prev->next = newNode;
        head.prev = newNode;
    }
    node* removeK(node* ptr, int k){
        for(int i = 0 ; i < k; i++){
            if(ptr->next == &head){
                ptr = ptr->next;
            }
            ptr = ptr->next;
        }
        if (ptr->next == &head){
            ptr = ptr->next;
        }
        node* deleteNode = ptr->next;
        ptr->next = deleteNode->next;
        deleteNode->next->prev = ptr;
        // delete deleteNode;
        return ptr;
    }

    int findTheWinner(int n, int k) {
        for(int i = 1; i <= n; i++){
            insertLast(i);
        }
        node* ptr = &head;
        while(n-- > 1){
            ptr = removeK(ptr, k-1);
            cout << ptr->next->val << endl;
        }
        return head.next->val;
    }
};

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

Crawler Log Folder  (0) 2025.02.02
Average Waiting Time  (0) 2025.02.02
Water Bottles  (0) 2025.02.02
Pass the Pillow  (0) 2025.02.02
Find the Minimum and Maximum Number of Nodes Between Critical Points  (0) 2025.02.02
블로그 이미지

짬뽕얼큰하게

,

Water Bottles

알고리즘 2025. 2. 2. 20:46

summary

  • Maximum Water Bottles that can be drunk

approach

  • This solution uses a greedy approach, starting with the maximum possible number of full bottles and then repeatedly exchanging empty bottles for full ones until no more exchanges are possible.

complexity

  • O(n), where n is the number of full bottles

explain

  • The solution starts by adding the initial number of full bottles to the total count of water bottles that can be drunk
  • It then enters a loop where it repeatedly exchanges empty bottles for full ones until no more exchanges are possible
  • In each iteration of the loop, it calculates the number of full bottles that can be obtained from the available empty bottles and adds this to the total count
  • The number of full bottles that can be obtained in each iteration is calculated as the integer division of the number of available empty bottles by the exchange rate, plus the remainder of the division, which represents the number of empty bottles that are not enough to exchange for a full bottle.

Solution Code:


class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        int ans = 0;
        ans += numBottles;
        while(numBottles >= numExchange){
            ans += numBottles/numExchange;
            numBottles = (numBottles/numExchange) + (numBottles % numExchange);
        }
        return ans;
    }
};

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

Average Waiting Time  (0) 2025.02.02
Find the Winner of the Circular Game  (0) 2025.02.02
Pass the Pillow  (0) 2025.02.02
Find the Minimum and Maximum Number of Nodes Between Critical Points  (0) 2025.02.02
Merge Nodes in Between Zeros  (0) 2025.02.02
블로그 이미지

짬뽕얼큰하게

,

Pass the Pillow

알고리즘 2025. 2. 2. 20:43

summary

  • The problem is to find the index of the person holding the pillow after a given time in a line of people passing the pillow in both directions.

approach

  • The approach is to calculate the number of complete rounds the pillow makes and the remaining time, then determine the person holding the pillow based on the time.

complexity

  • O(1)

explain

  • The code first calculates the number of complete rounds the pillow makes by dividing the time by the number of people minus one
  • If the time is odd, the remaining time is the person holding the pillow, otherwise, it is the person after the remaining time
  • The code returns the index of the person holding the pillow.

Solution Code:


class Solution {
public:
    int passThePillow(int n, int time) {
        int a = time / (n-1);
        if(a&1){
            return n - time % (n-1);
        } else{
            return 1 + time % (n-1);
        }
    }
};

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

Find the Winner of the Circular Game  (0) 2025.02.02
Water Bottles  (0) 2025.02.02
Find the Minimum and Maximum Number of Nodes Between Critical Points  (0) 2025.02.02
Merge Nodes in Between Zeros  (0) 2025.02.02
Minimum Difference Between Largest and Smallest Value in Three Moves  (0) 2025.02.02
블로그 이미지

짬뽕얼큰하게

,

Find the Minimum and Maximum Number of Nodes Between Critical Points

알고리즘 2025. 2. 2. 20:39

summary

  • Finding critical points in a linked list and calculating the minimum and maximum distances between them.

approach

  • The approach used is to traverse the linked list and keep track of the previous node's value
  • When a new node is encountered, it checks if the current node and the next node have the same value
  • If they do not, and the current node's value is greater than the previous node's value, or less than the previous node's value, it checks if the current node is a local maxima or minima
  • If it is, it adds the current index to the vector of nodes between critical points
  • The minimum distance is calculated by finding the minimum difference between any two indices in the vector, and the maximum distance is calculated by finding the maximum difference between any two indices in the vector.

complexity

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

explain

  • The code first initializes a variable `prev` to -1 to keep track of the previous node's value
  • It then traverses the linked list, and for each node, it checks if the current node and the next node have the same value
  • If they do not, and the current node's value is greater than the previous node's value, or less than the previous node's value, it checks if the current node is a local maxima or minima
  • If it is, it adds the current index to the vector of nodes between critical points
  • The minimum distance is calculated by finding the minimum difference between any two indices in the vector, and the maximum distance is calculated by finding the maximum difference between any two indices in the vector
  • If there are fewer than two critical points, the function returns [-1, -1].

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:
    int prev = -1;
    vector nodesBetweenCriticalPoints(ListNode* head) {
        ListNode* ptr;
        vector ansVector;
        int minVal = 1234567890;
        int idx;
        for(ptr = head, idx=0; ptr->next != nullptr; ptr = ptr->next, idx++){
            if(prev == -1){
                prev = ptr->val;
                continue;
            }
            if (ptr->next->val > ptr->val && prev > ptr->val){
                if (!ansVector.empty()){
                    minVal = min(minVal, idx - ansVector.back());
                }
                ansVector.push_back(idx);
            } else if(ptr->next->val < ptr->val && prev < ptr->val){
                if (!ansVector.empty()){
                    minVal = min(minVal, idx - ansVector.back());
                }
                ansVector.push_back(idx);
            }
            prev = ptr->val;
        }
        if (ansVector.size() < 2) return {-1, -1};
        return {minVal, ansVector.back() - ansVector[0]};
    }
};

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

Water Bottles  (0) 2025.02.02
Pass the Pillow  (0) 2025.02.02
Merge Nodes in Between Zeros  (0) 2025.02.02
Minimum Difference Between Largest and Smallest Value in Three Moves  (0) 2025.02.02
Intersection of Two Arrays II  (0) 2025.02.02
블로그 이미지

짬뽕얼큰하게

,

Merge Nodes in Between Zeros

알고리즘 2025. 2. 2. 20:34

summary

  • Given a linked list containing integers separated by 0's, merge every two consecutive 0's into a single node whose value is the sum of all the merged nodes.

approach

  • This problem can be solved by iterating through the linked list and maintaining a running sum of nodes between two consecutive 0's
  • When a 0 is encountered, a new node is created with the sum of the nodes between the previous 0 and the current 0, and the sum is reset to 0.

complexity

  • O(n), where n is the number of nodes in the linked list, because each node is visited once.

explain

  • The solution code first initializes a pointer to the second node in the list (after the first node) and a pointer to the new node that will be created
  • It also initializes a sum variable to 0
  • Then, it iterates through the list, adding each node's value to the sum if the current node is not a 0
  • When a 0 is encountered, a new node is created with the sum of the nodes between the previous 0 and the current 0, and the sum is reset to 0
  • The new node is linked to the previous node, and the previous node becomes the current node
  • This process continues until the end of the list is reached, at which point the new node is returned as the head of the modified linked list.

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:
    
    ListNode* mergeNodes(ListNode* head) {
        ListNode* answer = nullptr;
        ListNode* ptr2;
        int sum = 0;
        for (ListNode* ptr = head-> next; ptr != nullptr; ptr = ptr->next){
            if(ptr->val == 0){
                if (answer == nullptr){
                    answer = new ListNode(sum);
                    ptr2 = answer;
                } else {
                    ptr2->next = new ListNode(sum);
                    ptr2 = ptr2->next;
                }
                sum = 0;
            } else {
                sum += ptr->val;
            }
        }
        return answer;
    }
};

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

Pass the Pillow  (0) 2025.02.02
Find the Minimum and Maximum Number of Nodes Between Critical Points  (0) 2025.02.02
Minimum Difference Between Largest and Smallest Value in Three Moves  (0) 2025.02.02
Intersection of Two Arrays II  (0) 2025.02.02
Three Consecutive Odds  (0) 2025.02.02
블로그 이미지

짬뽕얼큰하게

,

Minimum Difference Between Largest and Smallest Value in Three Moves

알고리즘 2025. 2. 2. 20:30

summary

  • Find the minimum difference between the largest and smallest value of an integer array after performing at most three moves.

approach

  • This solution uses a depth-first search (DFS) approach to try all possible moves and find the minimum difference
  • The DFS function recursively tries different moves and updates the minimum difference
  • The main function first sorts the array and then calls the DFS function with the initial minimum and maximum values.

complexity

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

explain

  • The solution starts by sorting the input array
  • Then, it uses a DFS function to try all possible moves
  • The DFS function takes the current array, the current depth (which represents the number of moves made so far), the left and right indices of the current subarray
  • If the current depth is 3, it means we have made 3 moves, so it returns the difference between the maximum and minimum values in the current subarray
  • Otherwise, it recursively tries two possible moves: moving the left element to the right and moving the right element to the left
  • The minimum difference found by these two recursive calls is returned
  • The main function calls the DFS function with the initial minimum and maximum values and returns the result.

Solution Code:


int abs(int x){
    return x < 0 ? -x : x;
}
class Solution {
public:
    int dfs(vector&nums, int depth, int l, int r){
        if (depth == 3){
            return nums[r] - nums[l];
        }
        int res = dfs(nums, depth+1, l+1, r);
        res = min(res, dfs(nums, depth+1, l, r-1));
        return res;
    }
    int minDifference(vector& nums) {
        if (nums.size() <= 3) return 0;
        sort(nums.begin(), nums.end());
        int l = 0;
        int r = nums.size() - 1;
        return dfs(nums, 0, l, r);
    }
};

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

Find the Minimum and Maximum Number of Nodes Between Critical Points  (0) 2025.02.02
Merge Nodes in Between Zeros  (0) 2025.02.02
Intersection of Two Arrays II  (0) 2025.02.02
Three Consecutive Odds  (0) 2025.02.02
Remove Max Number of Edges to Keep Graph Fully Traversable  (0) 2025.02.02
블로그 이미지

짬뽕얼큰하게

,

Intersection of Two Arrays II

알고리즘 2025. 2. 2. 20:26

summary

  • Given two integer arrays, return an array of their intersection
  • Each element in the result must appear as many times as it shows in both arrays.

approach

  • The approach used is to first count the occurrences of each element in the first array using an unordered map
  • Then, for each element in the second array, if it exists in the map and its count is greater than 0, decrement the count and add the element to the result array.

complexity

  • O(n + m) where n and m are the sizes of the input arrays

explain

  • The solution iterates over the first array to count the occurrences of each element in the unordered map
  • Then, it iterates over the second array to find elements that exist in the map and add them to the result array
  • This approach ensures that each element in the result appears as many times as it shows in both arrays.

Solution Code:


class Solution {
public:
    vector intersect(vector& nums1, vector& nums2) {
        vector answer;
        unordered_map cnt;
        for(int i = 0 ; i < nums1.size(); i++){
            cnt[nums1[i]]++;
        }
        for(int i = 0 ; i < nums2.size(); i++){
            if(cnt[nums2[i]]){
                cnt[nums2[i]]--;
                answer.push_back(nums2[i]);
            }
        }
        return answer;
    }
};

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

Merge Nodes in Between Zeros  (0) 2025.02.02
Minimum Difference Between Largest and Smallest Value in Three Moves  (0) 2025.02.02
Three Consecutive Odds  (0) 2025.02.02
Remove Max Number of Edges to Keep Graph Fully Traversable  (0) 2025.02.02
Find Center of Star Graph  (0) 2025.02.02
블로그 이미지

짬뽕얼큰하게

,

Three Consecutive Odds

알고리즘 2025. 2. 2. 20:17

summary

  • Given an integer array, return true if there are three consecutive odd numbers in the array, otherwise return false.

approach

  • The solution uses a counter to keep track of the number of consecutive odd numbers
  • It iterates over the array, incrementing the counter whenever it encounters an odd number and resetting it whenever it encounters an even number
  • If the counter reaches 3, it immediately returns true
  • If it iterates over the entire array without finding three consecutive odd numbers, it returns false.

complexity

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

explain

  • The solution has a time complexity of O(n) because it makes a single pass over the array
  • The space complexity is O(1) because it uses a constant amount of space to store the counter.

Solution Code:


class Solution {
public:
    bool threeConsecutiveOdds(vector& arr) {
        int cnt = 0;
        for(int i = 0 ; i < arr.size(); i++){
            if(arr[i] & 1){
                cnt++;
            } else {
                cnt = 0;
            }
            if (cnt >= 3) return true;
        }
        return false;
    }
};

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

Minimum Difference Between Largest and Smallest Value in Three Moves  (0) 2025.02.02
Intersection of Two Arrays II  (0) 2025.02.02
Remove Max Number of Edges to Keep Graph Fully Traversable  (0) 2025.02.02
Find Center of Star Graph  (0) 2025.02.02
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit  (0) 2025.02.02
블로그 이미지

짬뽕얼큰하게

,

Remove Max Number of Edges to Keep Graph Fully Traversable

알고리즘 2025. 2. 2. 19:56

summary

  • This problem involves finding the maximum number of edges that can be removed from an undirected graph so that it can still be fully traversed by both Alice and Bob.

approach

  • The approach used in this solution is to first separate the edges into three types: Type 1 (can be traversed by Alice only), Type 2 (can be traversed by Bob only), and Type 3 (can be traversed by both Alice and Bob)
  • Then, we use disjoint sets to keep track of the connected components of the graph for each type of edge
  • We remove the maximum number of edges of Type 3 while ensuring that the graph remains fully traversable by both Alice and Bob.

complexity

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

explain

  • The solution starts by separating the edges into three types and initializing two disjoint sets for Alice and Bob
  • It then sorts the edges of each type by their type and uses the disjoint sets to keep track of the connected components of the graph
  • The solution then removes the maximum number of edges of Type 3 while ensuring that the graph remains fully traversable by both Alice and Bob
  • If the graph is not fully traversable, the solution returns -1
  • The time complexity is O(n log n + m log m + n log n) due to the sorting and disjoint set operations.

Solution Code:




class Solution {
public:
    int u1[100001];
    int u2[100001];
    
    vector> edgesType1;
    vector> edgesType2;
    static bool cmp1(vector &a, vector &b){
        return a[0] > b[0];
    }
    static bool cmp2(vector &a, vector &b){
        return a[0] > b[0];
    }
    int disjoint(int* u, int x){
        if(u[x] == x) return x;
        return u[x] = disjoint(u, u[x]);
    }
    int maxNumEdgesToRemove(int n, vector>& edges) {
        edgesType1.clear();
        edgesType2.clear();
        int edgeSize = edges.size();
        for(int i = 1; i <= n; i++){
            u1[i] = i;
            u2[i] = i;
        }
        for(int i = 0; i < edges.size(); i++){
            if(edges[i][0] == 1){
                edgesType1.push_back(edges[i]);
            } else if (edges[i][0] == 2){
                edgesType2.push_back(edges[i]);
            } else{
                edgesType1.push_back(edges[i]);
                edgesType2.push_back(edges[i]);
            }
        }
        sort(edgesType1.begin(), edgesType1.end(), cmp1);
        sort(edgesType2.begin(), edgesType2.end(), cmp2);

        int type3 = 0;
        int cnt = 0;
        for (int idx = 0 ; idx < edgesType1.size(); idx++) {
            int type = edgesType1[idx][0];
            int a = edgesType1[idx][1];
            int b = edgesType1[idx][2];
            if(disjoint(u1, a) == disjoint(u1, b)){
                continue;
            }
            cnt++; 
            u1[disjoint(u1, a)] = disjoint(u1, b);
            if (type == 3){
                type3 += 1;
            }
            if (cnt == n -1) break;
        }
        if (cnt != n-1) return -1;
        cnt = 0;
        for (int idx = 0 ; idx < edgesType2.size(); idx++) {
            int type = edgesType2[idx][0];
            int a = edgesType2[idx][1];
            int b = edgesType2[idx][2];
            if(disjoint(u2, a) == disjoint(u2, b)){
                continue;
            }
            cnt++; 
            u2[disjoint(u2, a)] = disjoint(u2, b);
            if (cnt == n -1) break;
        }
        if (cnt != n-1) return -1;

        return edges.size() - (n - 1) - (n - 1) + type3;
    }
};

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

Intersection of Two Arrays II  (0) 2025.02.02
Three Consecutive Odds  (0) 2025.02.02
Find Center of Star Graph  (0) 2025.02.02
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit  (0) 2025.02.02
Special Array I  (0) 2025.02.02
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/02   »
일 월 화 수 목 금 토
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

티스토리툴바