'2025/02'에 해당되는 글 176건

Leetcode Problem:

• Find if Array Can Be Sorted

Summary

• Given an array of positive integers, determine if it can be sorted in ascending order by swapping adjacent elements with the same number of set bits.

Approach

• The solution uses a two-pass approach to track the maximum and minimum numbers encountered so far
• It also keeps track of the number of set bits for each number
• If a number with more set bits is found after a number with the same number of set bits, the function returns false
• If all numbers can be sorted, the function returns true.

Complexity

• O(n) where n is the number of elements in the array, as each element is visited once.

Explanation

• The solution works by iterating through the array and tracking the number of set bits for each number
• If a number with more set bits is found after a number with the same number of set bits, the function returns false
• If all numbers can be sorted, the function returns true
• The time complexity is O(n) because each element is visited once, and the space complexity is O(1) because only a constant amount of space is used.

Solution Code:

class Solution {
public:
    int getOneCnt(int num){
        int cnt = 0;
        while(num){
            cnt++;
            num &= num-1;
        }
        return cnt;
    }
    vector arr;
    bool canSortArray(vector& nums) {
        int beforeCnt = getOneCnt(nums[0]);
        int beforeMax = 0;
        int maxNum = nums[0];
        for(int i = 1 ; i < nums.size(); i++){
            int cnt = getOneCnt(nums[i]);
            if( cnt != beforeCnt){
                if(maxNum > nums[i]) return false;
                beforeMax = maxNum;
                maxNum = nums[i];
                beforeCnt = cnt;
                continue;
            }
            if(beforeMax > nums[i]) return false;
            if(maxNum < nums[i]){
                maxNum = nums[i];
            }
        }

        return true;
    }
};

Leetcode Problem:

• Find Unique Binary String

Summary

• Given an array of unique binary strings, return a binary string that does not appear in the array.

Approach

• The solution uses a set data structure to store the binary numbers represented by the input strings
• It then iterates over all possible binary numbers of the same length as the input strings, checks if each number is in the set, and returns the first number that is not in the set.

Complexity

• O(2^n * n) where n is the length of the input strings

Explanation

• The solution first converts each binary string to a decimal number using the `makeNum` function
• It then stores these decimal numbers in a set
• The `makeStr` function is used to convert a decimal number back to a binary string
• The solution then iterates over all possible binary numbers of the same length as the input strings, checks if each number is in the set, and returns the first number that is not in the set
• This approach ensures that the solution finds the first binary string that does not appear in the input array.

Solution Code:

class Solution {
public:
    int makeNum(string s){
        int num = 0;
        for(int i = 0 ; i < s.size(); i++){
            num *= 2;
            num += s[i] - '0';
        }
        return num;
    }
    string makeStr(int num, int length){
        string res = "";
        for(int i = 0 ; i < length; i++){
            res = string(1, '0'+(num %2)) + res;
            num /= 2;
        }
        return res;
    }
    bool set[1<<16];
    string findDifferentBinaryString(vector& nums) {
        int length = nums[0].size();
        for(int i = 0 ; i < nums.size(); i++){
            set[makeNum(nums[i])] = true;
        }
        for(int i = 0 ; i < (1 << 16); i++){
            if(set[i]){
                continue;
            }
            return makeStr(i, length);
        }
        return "";
    }
};

Leetcode Problem:

• Minimum Number of Changes to Make Binary String Beautiful

Summary

• The problem requires to find the minimum number of changes required to make a binary string beautiful
• A beautiful string is a string that can be partitioned into substrings with even length and only containing 1's or 0's.

Approach

• The approach is to iterate over the string in steps of 2 and count the number of pairs of characters that are not the same
• If the pair is not the same, it means that the string needs to be changed to make it beautiful, so we increment the result.

Complexity

• O(n/2) = O(n), where n is the length of the string.

Explanation

• The solution iterates over the string in steps of 2, which is because each pair of characters is considered together
• If the pair of characters is not the same, it means that the string needs to be changed to make it beautiful, so we increment the result
• The time complexity is O(n) because we are iterating over the string once.

Solution Code:

class Solution {
public:
    int minChanges(string s) {
        int res = 0;
        for(int i = 0 ; i < s.size(); i += 2){
            if ((s[i] == '0' && s[i+1] == '0') || (s[i] == '1' && s[i+1] == '1')){
                continue;
            }
            res++;
        }
        return res;
    }
};

Leetcode Problem:

• String Compression III

Summary

• Given a string word, compress it using the algorithm where a maximum length prefix of a single character c repeating at most 9 times is removed, and the length of the prefix followed by c is appended to the compressed string.

Approach

• The approach used is to iterate through the input string and whenever a different character is encountered, the length of the previous character's prefix is appended to the compressed string, followed by the character
• This process continues until the end of the string.

Complexity

• O(n), where n is the length of the input string, because each character in the string is visited once.

Explanation

• The code uses a dynamic programming approach to solve the problem
• It first initializes a counter cnt to keep track of the length of the current character's prefix
• It then iterates through the input string, and whenever a different character is encountered, it calculates the length of the previous character's prefix (a and b) and appends it to the compressed string
• The counter cnt is then reset to 0 and the process continues until the end of the string.

Solution Code:

class Solution {
public:
    int str_cnt[256];
    string compressedString(string word) {
        int cnt = 0;
        char beforeChar = 'a'-1;
        string res = "";
        for(char c : word) {
            if(c != beforeChar){
                int a = cnt / 9;
                for(int i = 0 ; i < a; i++){
                    res += "9" + string(1, beforeChar);
                }
                int b = cnt % 9;
                if (b > 0){
                    res += to_string(b) + string(1, beforeChar);
                }
                cnt = 0;
            }
            cnt++;
            beforeChar = c;
        }
        int a = cnt / 9;
        for(int i = 0 ; i < a; i++){
            res += "9" + string(1, beforeChar);
        }
        int b = cnt % 9;
        if (b > 0){
            res += to_string(b) + string(1, beforeChar);
        }
        
        return res;
    }
};

Leetcode Problem:

• Rotate String

Summary

• Given a string s and a goal, return true if s can become goal after some number of shifts on s.

Approach

• The solution uses a while loop to simulate the process of shifting characters in s
• It checks if the current state of s is equal to the goal after each shift
• If it finds a match, it returns true
• If it exhausts all possible shifts without finding a match, it returns false.

Complexity

• O(n*m) where n is the length of s and m is the length of goal
• This is because in the worst case, the solution checks every possible state of s, which is a permutation of the characters in s.

Explanation

• The solution starts by initializing a variable N to the length of s
• It then enters a while loop that runs N times
• In each iteration, it checks if the current state of s is equal to the goal
• If it is, it returns true
• If not, it shifts the characters in s one position to the right by concatenating s with its first character and then removing the first character
• This effectively moves the leftmost character to the rightmost position
• If it exhausts all possible shifts without finding a match, it returns false.

Solution Code:

class Solution {
public:
    bool rotateString(string s, string goal) {
        int N = s.size();
        while(N--){
            if(s.compare(goal) == 0){
                return true;
            }
            s = s + s[0];
            s = s.substr(1);
        }

        return false;
    }
};

Leetcode Problem:

• Delete Characters to Make Fancy String

Summary

• The problem is to delete the minimum possible number of characters from a string to make it a fancy string, where no three consecutive characters are equal.

Approach

• The approach used is to iterate through the string and check for consecutive characters
• If three consecutive characters are equal, they are skipped
• Otherwise, they are added to the result string.

Complexity

• O(n), where n is the length of the string

Explanation

• The solution code initializes a string `ss` with the first character of the input string
• It then iterates through the rest of the string, checking for consecutive characters
• If three consecutive characters are equal, they are skipped
• Otherwise, they are added to the result string
• The code also keeps track of the count of consecutive characters and resets it when a different character is encountered.

Solution Code:

class Solution {
public:
    string makeFancyString(string s) {
        string ss = string(1,s[0]);
        int repeat_cnt = 1;
        char before_char = s[0];
        for(int i = 1 ;  i < s.size(); i++){
            if (before_char == s[i]){
                repeat_cnt++;
                if(repeat_cnt >= 3) continue;
            } else {
                repeat_cnt = 1;
            }
            ss += s[i];
            before_char = s[i];
        }
        return ss;
    }
};

Leetcode Problem:

• Minimum Total Distance Traveled

Summary

• Minimum Total Distance for Robots to Reach Factories

Approach

• Dynamic Programming with Memoization

Complexity

• O(n*m*log(n)+m*log(m))

Explanation

• This solution sorts the robots and factories by position, then uses dynamic programming with memoization to calculate the minimum total distance
• The `calculateMinDistance` function recursively tries two options: assigning the current robot to the current factory and skipping the current factory for the current robot
• The minimum of these two options is stored in the memo table to avoid repeated calculations.

Solution Code:

class Solution {
public:
    long long minimumTotalDistance(vector& robot,
                                   vector>& factory) {
        // Sort robots and factories by position
        sort(robot.begin(), robot.end());
        sort(factory.begin(), factory.end());

        // Flatten factory positions according to their capacities
        vector factoryPositions;
        for (auto& f : factory)
            for (int i = 0; i < f[1]; i++) factoryPositions.push_back(f[0]);

        int robotCount = robot.size(), factoryCount = factoryPositions.size();
        vector> memo(robotCount,
                                       vector(factoryCount, -1));

        // Recursively calculate minimum total distance with memoization
        return calculateMinDistance(0, 0, robot, factoryPositions, memo);
    }

    long long calculateMinDistance(int robotIdx, int factoryIdx,
                                   vector& robot,
                                   vector& factoryPositions,
                                   vector>& memo) {
        // All robots assigned
        if (robotIdx == robot.size()) return 0;
        // No factories left to assign
        if (factoryIdx == factoryPositions.size()) return 1e12;
        // Check memo
        if (memo[robotIdx][factoryIdx] != -1) return memo[robotIdx][factoryIdx];

        // Option 1: Assign current robot to current factory
        long long assign = abs(robot[robotIdx] - factoryPositions[factoryIdx]) +
                           calculateMinDistance(robotIdx + 1, factoryIdx + 1,
                                                robot, factoryPositions, memo);

        // Option 2: Skip current factory for the current robot
        long long skip = calculateMinDistance(robotIdx, factoryIdx + 1, robot,
                                              factoryPositions, memo);

        return memo[robotIdx][factoryIdx] =
                   min(assign, skip);  // Take the minimum and store in memo
    }
};

Leetcode Problem:

• The k-th Lexicographical String of All Happy Strings of Length n

Summary

• This problem is to find the kth happy string of a given length n, where happy string is a string that consists only of letters a, b, c and s[i]!= s[i + 1] for all values of i from 1 to n - 1.

Approach

• The approach used in this solution is a recursive function that generates all happy strings of a given length n
• The function uses a dynamic programming approach to keep track of the number of happy strings generated so far and returns the kth string when k is reached.

Complexity

• O(3^n) because in the worst case, for each position in the string, there are 3 possible choices for the character, and this choice is made n times.

Explanation

• The solution uses a recursive function getHappyString that takes four parameters: n (the length of the string), k (the position of the string we want to find), depth (the current position in the string), and res (the string generated so far)
• The function first checks if the length of the string is equal to the depth
• If it is, it increments the count of happy strings and checks if the count is equal to k
• If it is, it returns the string
• If not, it returns an empty string
• If the length of the string is not equal to the depth, the function loops through each character in the set {a, b, c} and recursively calls itself with the next depth and the current character appended to the result string
• If the recursive call returns a non-empty string, it returns that string
• Otherwise, it returns an empty string.

Solution Code:

class Solution {
public:
    char c[3] = {'a', 'b', 'c'};
    int cnt;
    string getHappyString(int n, int k, int depth = 0, string res = "") {
        if(n == depth){
            cnt++;
            if(cnt == k){
                return res;
            }
            return "";
        }
        for(int i = 0 ; i < 3; i++){
            if(depth != 0 && res[depth-1] == c[i]){
                continue;
            }
            string ans = getHappyString(n, k, depth + 1, res + c[i]);
            if(ans.size() != 0){
                return ans;
            }
        }
        return "";
    }
};

Leetcode Problem:

• Minimum Number of Removals to Make Mountain Array

Summary

• Given an integer array nums, return the minimum number of elements to remove to make nums a mountain array.

Approach

• Dynamic programming approach to solve the problem
• Two arrays dp1 and dp2 are used to store the maximum number of elements that can be removed to make the left and right parts of the array a mountain array respectively.

Complexity

• O(n^2) where n is the size of the input array nums

Explanation

• The dp1 array is used to store the maximum number of elements that can be removed to make the left part of the array a mountain array
• The dp1 array is filled in a bottom-up manner
• For each element in the array, the maximum number of elements that can be removed to make the left part of the array a mountain array is updated
• The dp2 array is used to store the maximum number of elements that can be removed to make the right part of the array a mountain array
• The dp2 array is also filled in a bottom-up manner
• For each element in the array, the maximum number of elements that can be removed to make the right part of the array a mountain array is updated
• Finally, the minimum number of elements that need to be removed to make the entire array a mountain array is calculated by iterating over the array and checking if the current element is greater than or equal to the previous element
• If it is, then the minimum number of elements that need to be removed is updated.

Solution Code:

class Solution {
public:
    int dp1[1001];
    int dp2[1001];
    int minimumMountainRemovals(vector& nums) {
        int N = nums.size();
        dp1[N - 1] = 1;
        for(int i = N-2; i>= 0; i--){
            dp1[i] = 1;
            for(int j = i + 1; j < N; j++){
                if(nums[j]< nums[i]){
                    dp1[i] = max(dp1[i], dp1[j] + 1);
                }
            }
        }

        dp2[0] = 1;
        for(int i = 1 ; i < nums.size(); i++){
            dp2[i] = 1;
            for(int j = i -1; j >= 0; j--){
                if(nums[j]< nums[i]){
                    dp2[i] = max(dp2[i], dp2[j] + 1);
                }
            }
        }
        int res = 0;
        for(int i = 1 ; i< N-1; i++){
            if(nums[i-1] >= nums[i]) continue;
            int j_max = 0;
            bool success = false;
            for(int j = i + 1; j < N; j++){
                if(nums[i] <= nums[j]){
                    continue;
                }
                success = true;
                j_max = max(j_max, dp1[j]);
            }
            if (success)
                res = max(res, j_max + dp2[i]);
        }
        return N -res;
    }
};

Leetcode Problem:

• Maximum Number of Moves in a Grid

Summary

• This problem requires finding the maximum number of moves that can be performed in a grid while following certain rules.

Approach

• The approach used is a breadth-first search (BFS) algorithm
• It starts from the first column of the grid and explores all possible cells that can be reached from each cell
• The algorithm keeps track of the number of moves made and updates the maximum number of moves found so far.

Complexity

• O(R*C) where R is the number of rows and C is the number of columns in the grid.

Solution Code:

struct _pair{
    int r;
    int c;
};
struct _queue{
    _pair arr[1000001];
    int front = 0;
    int rear = 0;
    void pop(){
        front++;
    }
    void push(_pair a){
        arr[rear++] = a;
    }
    _pair peek(){
        return arr[front];
    }
    bool empty(){
        return front == rear;
    }
    
};
class Solution {
public:
    int visited[1000][1000];
    _queue que;
    
    int maxMoves(vector>& grid) {
        int dy[] = {1, -1, 0};
        int dx[] = {1, 1, 1};
        int R = grid.size();
        int C = grid[0].size();
        int ans = 0;
        for(int i = 0 ; i < grid.size(); i++){
            que.push({i, 0});
            visited[i][0] = 0;
        }
        while(!que.empty()){
            _pair num = que.peek();
            que.pop();
            ans = max(ans, visited[num.r][num.c]);
            for(int i = 0 ; i < 3; i++){
                int ny = num.r + dy[i];
                int nx = num.c + dx[i];
                if(ny < 0 || ny >= R || nx < 0 || nx >= C || 
                    visited[num.r][num.c] + 1 <= visited[ny][nx] ||
                    grid[num.r][num.c] >= grid[ny][nx]){
                    continue;
                }
                visited[ny][nx] = visited[num.r][num.c] + 1;
                que.push({ny, nx});
            }
        }
        return ans;
    }
};