koenjazh-CNfresde
짬뽕얼큰하게의 맨땅에 헤딩 :: 짬뽕얼큰하게의 맨땅에 헤딩

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
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

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

티스토리툴바