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

Leetcode Problem:

• Step-By-Step Directions From a Binary Tree Node to Another

Summary

• This problem requires finding the shortest path from a start node to a destination node in a binary tree
• The path is represented as a string of 'L', 'R', and 'U' characters, where 'L' represents going to the left child, 'R' represents going to the right child, and 'U' represents going to the parent node.

Approach

• This solution uses a depth-first search approach to find the shortest path from the start node to the destination node
• It first searches for the start node and stores its path in the rootToStart vector
• Then, it searches for the destination node and stores its path in the rootToDest vector
• Finally, it constructs the shortest path by concatenating the 'U' characters to the start of the path and the 'L' and 'R' characters to the end of the path.

Complexity

• The time complexity of this solution is O(n), where n is the number of nodes in the tree
• This is because each node is visited once during the depth-first search
• The space complexity is also O(n) due to the storage of the paths in the rootToStart and rootToDest vectors.

Explain

• The solution uses two vectors, rootToStart and rootToDest, to store the paths from the start node to the destination node
• The searchPath function is used to search for the start node and the destination node, and it uses a depth-first search approach to traverse the tree
• The getDirections function is used to construct the shortest path by concatenating the 'U' characters to the start of the path and the 'L' and 'R' characters to the end of the path.

Solution Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

vector rootToStart;
vector rootToDest;
vector rootToDestChar;
class Solution {
public:
    bool searchPath(TreeNode* ptr, int dest, vector &path){
        if (ptr == nullptr) return false;
        if (ptr->val == dest) {
            path.push_back(dest);
            return true;
        }
        path.push_back(ptr->val);
        rootToDestChar.push_back('L');
        if (searchPath(ptr->left, dest, path)){
            return true;
        }
        rootToDestChar.pop_back();
        rootToDestChar.push_back('R');
        if (searchPath(ptr->right, dest, path)){
            return true;
        }
        rootToDestChar.pop_back();
        path.pop_back();
        return false;
    }
    string getDirections(TreeNode* root, int startValue, int destValue) {
        rootToStart.clear();
        rootToDest.clear();
        searchPath(root, startValue, rootToStart);
        rootToDestChar.clear();
        searchPath(root, destValue, rootToDest);
        
        string res = "";
        int cnt = 0;
        while(cnt < rootToStart.size() && cnt < rootToDest.size() && rootToStart[cnt] == rootToDest[cnt]) cnt++;
        for(int i = 0; i < rootToStart.size() - cnt; i++){
            res += "U";
        }
        for(int i = cnt-1 ; i < rootToDestChar.size(); i++){
            res += rootToDestChar[i];
        }
        return res;
    }
};

Leetcode Problem:

• Create Binary Tree From Descriptions

Summary

• Constructing a binary tree from given descriptions of parent-child relationships.

Approach

• We use a map to store the nodes of the binary tree, where the key is the node value and the value is a pointer to the node
• We also use another map to store the parent of each node
• We iterate through the descriptions and create the nodes and their children accordingly
• Finally, we find the root of the tree by following the parent map until we reach a node that has no parent.

Complexity

• O(n), where n is the number of descriptions, because we make a single pass through the descriptions to create the nodes and their children.

Explain

• The solution starts by creating two maps: `myMap` to store the nodes and `parentMap` to store the parent of each node
• We then iterate through the descriptions and create the nodes and their children accordingly
• If a node does not exist in `myMap`, we create it
• We then set the left or right child of the parent node based on the value of `isLeft`
• Finally, we find the root of the tree by following the parent map until we reach a node that has no parent
• The time complexity is O(n) because we make a single pass through the descriptions to create the nodes and their children.

Solution Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* createBinaryTree(vector>& descriptions) {
        map myMap;
        map parentMap;
        int root = descriptions[0][0];
        for(int i = 0 ; i < descriptions.size(); i++){
            int parent = descriptions[i][0];
            int child = descriptions[i][1];
            int isLeft = descriptions[i][2];
            parentMap[child] = parent;
            if (myMap.find(parent) == myMap.end()){
                myMap[parent] = new TreeNode(parent);
            }
            if (myMap.find(child) == myMap.end()){
                myMap[child] = new TreeNode(child);
            }
            if (isLeft == 1){
                myMap[parent]->left = myMap[child];
            } else {
                myMap[parent]->right = myMap[child];
            }
        }
        while(parentMap.find(root) != parentMap.end()){
            root = parentMap[root];
        }
        return myMap[root];
    }
};

Leetcode Problem:

• Maximum Score From Removing Substrings

Summary

• Given a string s and two integers x and y, find the maximum points that can be gained by removing substrings of 'ab' and 'ba' from s.

Approach

• The solution uses a two-step approach
• First, it removes all occurrences of 'ab' or 'ba' from the string s, depending on which one has a higher value
• Then, it removes the remaining 'ab' or 'ba' substrings from the resulting string
• The points gained for each step are added to the total score.

Complexity

• O(n), where n is the length of the string s
• This is because the solution makes two passes through the string s, one for each step.

Explain

• The solution starts by initializing two vectors, firstStep and secondStep, to store the characters of the string s after the first and second steps, respectively
• It also initializes the total score res to 0
• The solution then iterates over the string s, adding characters to firstStep and secondStep based on whether they are 'ab' or 'ba'
• If a character is 'ab' or 'ba', the solution checks if the last character in the vector is the same as the character in 'ab' or 'ba'
• If they are the same, the solution adds the points gained for the step to the total score and removes the character from the vector
• Otherwise, the solution adds the character to the vector
• Finally, the solution returns the total score.

Solution Code:

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        int res = 0;
        vector firstStep;
        string cmpStr;
        int maxScore = max(x, y);
        int minScore = min(x, y);
        if (x > y){
            cmpStr = "ab";
        } else {
            cmpStr = "ba";
        }

        for(int i = 0 ; i < s.size(); i++){
            if (firstStep.size() == 0 || s[i] != cmpStr[1]){
                firstStep.push_back(s[i]);
            } else {
                char c = firstStep.back();
                if (c == cmpStr[0]){
                    res += maxScore;
                    firstStep.pop_back();
                } else {
                    firstStep.push_back(s[i]);
                }
            }
        }
        vector secondStep;

        for(int i = 0 ; i < firstStep.size(); i++){
            if (secondStep.size() == 0 || firstStep[i] != cmpStr[0]){
                secondStep.push_back(firstStep[i]);
            } else {
                char c = secondStep.back();
                if (c == cmpStr[1]){
                    res += minScore;
                    secondStep.pop_back();
                }else {
                    secondStep.push_back(firstStep[i]);
                }
            }
        }
        return res;
    }
};

summary

• Given a string s that consists of lower case English letters and brackets, reverse the strings in each pair of matching parentheses, starting from the innermost one.

approach

• This solution uses a stack to keep track of the indices of the characters that need to be reversed
• When a closing parenthesis is encountered, the solution pops the corresponding opening parenthesis index from the stack, reverses the substring between these two indices, and then removes the opening parenthesis from the stack.

complexity

• O(N)

explain

• The solution iterates over the string s
• When it encounters an opening parenthesis, it pushes the current length of the string onto the stack
• When it encounters a closing parenthesis, it pops the corresponding opening parenthesis index from the stack, reverses the substring between these two indices, and then removes the opening parenthesis from the stack
• The solution continues this process until it has processed the entire string.

Solution Code:

class Solution {
public:
    
    string reverseParentheses(string s) {
        string res = "";
        int mystack[2001];
        int stackIdx = 0;
        int N = s.length();
        int idx = 0;
        for(int i = 0 ; i < N; i++){
            if (s[i] == '('){
                mystack[stackIdx++] = res.length();
            } else if (s[i] == ')'){
                int popIdx = mystack[--stackIdx];
                reverse(res.begin()+popIdx, res.end());
            } else {
                res += s[i];
            }
        }
        return res;
    }
};

summary

• The problem is to find the minimum number of operations needed to go back to the main folder after a series of change folder operations.

approach

• The solution uses a stack data structure to keep track of the current folder path
• When a folder operation is encountered, the corresponding action is performed on the stack
• If the operation is '../', the top element is removed from the stack
• If the operation is './', the top element is left unchanged
• If the operation is 'x/', the top element is replaced with 'x'
• The minimum number of operations needed to go back to the main folder is the number of times '../' is performed minus the number of times './' is performed.

complexity

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

explain

• The solution iterates over the logs array and performs the corresponding action on the stack for each operation
• The stack is used to keep track of the current folder path
• When the stack is empty and an '../' operation is encountered, the solution returns 0
• Otherwise, the solution returns the difference between the number of '../' operations and the number of './' operations.

Solution Code:

class Solution {
public:
    int minOperations(vector& logs) {
        int cnt = 0;
        for(int i = 0; i < logs.size(); i++){
            if(!logs[i].compare("../")){
                cnt = cnt - 1 < 0 ? 0 : cnt - 1;
            } else if (!logs[i].compare("./")){

            } else {
                cnt++;
            }
        }
        return cnt;
    }
};

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

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

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

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

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