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

Leetcode Problem:

• Minimum Number of Swaps to Make the String Balanced

Summary

• The problem is to find the minimum number of swaps required to make a given string of even length balanced.

Approach

• The approach used is to use a stack data structure to keep track of the opening brackets
• The stack is used to check if a closing bracket matches with the top of the stack
• If a match is found, the top of the stack is popped
• If no match is found, the current bracket is pushed into the stack
• After processing the entire string, the minimum number of swaps required to balance the string is calculated by dividing the number of remaining opening brackets by 2 and adding 1, and then dividing by 2.

Complexity

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

Explanation

• The provided solution code uses a stack to keep track of the opening brackets
• The stack is initialized as a private member of the Solution class
• In the minSwaps function, the code iterates over the string and checks if the stack is empty
• If the stack is empty, the current character is pushed into the stack
• If the stack is not empty, the top of the stack is checked with the current character
• If they match, the top of the stack is popped
• If they do not match, the current character is pushed into the stack
• After processing the entire string, the minimum number of swaps required to balance the string is calculated by dividing the number of remaining opening brackets by 2 and adding 1, and then dividing by 2.

Solution Code:

struct _stack{
    char arr[1000001];
    int top;
    _stack(){
        top = 0;
    }
    void push(char a){
        arr[top++] = a;
    }
    bool empty(){
        return top == 0;
    }
    char peek(){
        if(empty()) return -1;
        return arr[top-1];
    }
    void pop(){
        if(empty()) return;
        top--;
    }
};

class Solution {
public:
    _stack st;
    int minSwaps(string s) {
        int res = 0;
        for(int i = 0 ; i < s.size(); i++){
            if(st.empty()){
                st.push(s[i]);
                continue;
            }
            char a = st.peek();
            char b = s[i];
            if(a == '[' && b == ']'){
                st.pop();
                continue;
            } else{
                st.push(b);
            }
        }
        return (st.top/2+1)/2;
    }
};

Leetcode Problem:

• Minimum String Length After Removing Substrings

Summary

• Given a string of uppercase English letters, find the minimum possible length of the resulting string after removing any occurrences of the substrings "AB" or "CD".

Approach

• This problem is solved using a recursive approach where we try to remove the first occurrence of "AB" or "CD" from the string and then check if the resulting string can be further reduced
• If not, we return the current minimum length.

Complexity

• O(2^n) due to the recursive calls, where n is the length of the input string.

Explanation

• The solution starts by initializing the minimum length to the length of the input string
• Then, it iterates over the string and checks for the first occurrence of "AB" or "CD"
• If found, it recursively calls the function with the substring obtained by removing the found substring from the start of the string, and updates the minimum length if the resulting string has a smaller length
• This process continues until no more occurrences of "AB" or "CD" can be found in the string.

Solution Code:

class Solution {
public:
    int minLength(string s) {
        int ans = s.size();
        for(int i = 0 ; i < s.size(); i++){
            if (s.substr(i, 2).compare("AB") == 0){
                ans = min(ans, minLength(s.substr(0, i) + s.substr(i+2)));
                break;
            } else if (s.substr(i, 2).compare("CD") == 0){
                ans = min(ans, minLength(s.substr(0, i) + s.substr(i+2)));
                break;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Sentence Similarity III

Summary

• Two sentences are considered similar if it is possible to insert an arbitrary sentence (possibly empty) inside one of these sentences such that the two sentences become equal.

Approach

• The approach is to first find the longest common prefix of the two sentences
• If the prefix is empty, the sentences are not similar
• Otherwise, we check if the remaining part of the shorter sentence can be inserted between the words of the longer sentence to make them equal.

Complexity

• O(n), where n is the length of the shorter sentence.

Explanation

• We first find the longest common prefix of the two sentences by iterating through the characters of the sentences
• If the prefix is empty, we return false
• Otherwise, we check if the remaining part of the shorter sentence can be inserted between the words of the longer sentence to make them equal
• We do this by iterating through the remaining part of the shorter sentence and checking if each word matches the corresponding word in the longer sentence
• If we find a mismatch, we return false
• If we reach the end of the remaining part of the shorter sentence without finding a mismatch, we return true.

Solution Code:

class Solution {
public:
    bool areSentencesSimilar(string sentence1, string sentence2) {
        string t;
        if (sentence1.size() < sentence2.size()){
            t = sentence1;
            sentence1 = sentence2;
            sentence2 = t;
        }
        int lastSpace = -1;
        int i = 0;
        for( ; i < sentence2.size(); i++){
            if(sentence2[i] == sentence1[i] && sentence2[i] == ' '){
                lastSpace = i;
            }
            if (sentence1[i] != sentence2[i]) break;
        }
        if (i == sentence2.size() && sentence1[i] == ' ') return true;
        int s1_len = sentence1.size();
        int s2_len = sentence2.size();
        int before_idx = sentence1.size() - (s2_len - lastSpace);
        if (before_idx >= 0 && sentence1[before_idx] != ' ') return false;
        for(i = lastSpace+1; i < s2_len; i++){
            int s1_idx = sentence1.size() - (s2_len - i);
            if(s1_idx >= s1_len) return false;
            if(sentence1[s1_idx] != sentence2[i]) return false;
        }
        return true;
    }
};

Leetcode Problem:

• Construct the Lexicographically Largest Valid Sequence

Summary

• Given an integer n, find a sequence that satisfies the following conditions: 1 occurs once, each integer between 2 and n occurs twice, and the distance between the two occurrences of each integer is exactly i.

Approach

• The approach is to use a depth-first search (DFS) to try all possible sequences
• We start by initializing a vector to store the sequence and then call the DFS function
• In the DFS function, we try all possible numbers from n to 1, and for each number, we try to insert it into the sequence
• If the number is 1, we insert it at the first position
• If the number is not 1, we try to insert it at the position that is i steps away from the previous occurrence of the number, where i is the number itself
• We use a visited array to keep track of the numbers that have been tried, and we return false if we cannot find a valid sequence.

Complexity

• O(n^2 * 2^n) due to the recursive nature of the DFS function and the fact that we are trying all possible sequences.

Explanation

• The provided solution code uses a depth-first search (DFS) approach to try all possible sequences
• The DFS function is recursive and tries all possible numbers from n to 1
• For each number, it tries to insert it into the sequence
• If the number is 1, it inserts it at the first position
• If the number is not 1, it tries to insert it at the position that is i steps away from the previous occurrence of the number, where i is the number itself
• The solution uses a visited array to keep track of the numbers that have been tried, and it returns false if it cannot find a valid sequence
• The time complexity is O(n^2 * 2^n) due to the recursive nature of the DFS function and the fact that we are trying all possible sequences.

Solution Code:

class Solution {
public:
    int nextIdx(vector& ans){
        for(int i = 0 ; i < ans.size(); i++){
            if(ans[i] == -1)
                return i;
        }
        return -1;
    }
    int visited[21];
    bool dfs(int N, vector& ans){
        bool success = true;
        for(int i = 0 ; i < ans.size(); i++){
            if(ans[i] == -1){
                success = false;
                break;
            }
        }

        if(success){
            return true;
        }
        for(int i = N; i > 0; i--){
            if(visited[i]){
                continue;
            }
            visited[i] = true;
            int idx = nextIdx(ans);
            ans[idx] = i;
            if(i != 1){
                if(idx+i >= (2*N-1)  || ans[idx+i] != -1){
                    ans[idx] = -1;
                    visited[i] = false;
                    continue;
                } else{
                    ans[idx+i] = i;
                }
            }
            if(dfs(N, ans)){
                return true;
            }
            ans[idx] = -1;
            if(i != 1)
                ans[idx+i]= -1;
            visited[i] = false;
                   
        }
        return false;
    }
    vector constructDistancedSequence(int n) {
        vector ans;
        for(int i = 0; i < ((n << 1)-1) ; i++){
            ans.push_back(-1);
        }
        dfs(n, ans);
        return ans;   
    }
};

Leetcode Problem:

• Find the Punishment Number of an Integer

Summary

• This problem requires finding the punishment number of a given positive integer n
• The punishment number is the sum of squares of all integers i such that 1 <= i <= n and the decimal representation of i*i can be partitioned into contiguous substrings with integer values summing up to i.

Approach

• The solution uses a recursive approach with backtracking to find all possible partitions of i*i into contiguous substrings with integer values summing up to i
• It starts from the smallest possible value of i and checks all possible partitions of i*i
• If a valid partition is found, it adds the square of i to the result and moves on to the next value of i.

Complexity

• O(n * 6^6) where n is the input number, due to the recursive backtracking and the loop that generates all possible partitions of i*i.

Solution Code:

class Solution {
public:
    bool check_punishment(int num,vector& nums, int depth, int goal_num){
        if(num == 0){
            if(nums[0] == goal_num) return false;
            int sum = 0;
            for(int i = 0 ; i < nums.size(); i++){
                sum += nums[i];
            }
            if(sum == goal_num){
                return true;
            } else{
                return false;
            }
        }
        int pow = 10;
        for(int i = 1; i <= 6; i++){
            nums.push_back(num % pow);
            if(check_punishment(num/pow, nums, depth+1, goal_num)){
                nums.pop_back();
                return true;
            }
            pow *= 10;
            nums.pop_back();
        }
        return false;
    }
    int punishmentNumber(int n) {
        vector nums;
        int ans = 0;
        for(int i = 1; i <= n; i++){
            int pow = 10;
            for(int j = 1; j <= 6; j++){
                int nn = i * i;
                nums.push_back(nn % pow);
                if(check_punishment(nn/pow, nums, 1, i)){
                    nums.pop_back();
                    ans += nn;
                    break;
                }
                pow *= 10;
                nums.pop_back();
            }
        }
        
        return ans + 1;
    }
};

Leetcode Problem:

• Minimum Operations to Exceed Threshold Value II

Summary

• Find the minimum number of operations to make all elements in the array greater than or equal to k.

Approach

• Use a min-heap data structure to efficiently remove the two smallest elements from the array and add their minimum value times 2 plus their maximum value back into the array.

Complexity

• O(n log n) due to the heap operations, where n is the size of the input array.

Solution Code:

struct _heap{
    long long arr[400002];
    int size;
    _heap(){
        size = 1;
    }
    void push(long long a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && arr[idx/2] > arr[idx]){
            long long t = arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = t;
            idx /= 2;
        }
    }
    long long pop(){
        long long ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if (j >= size) break;
            if(j + 1 < size && arr[j] > arr[j + 1]){
                j++;
            }
            if(arr[i] > arr[j]){
                long long t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            }else{
                break;
            }
        }
        return ret;
    }
    bool empty(){
        return size == 1;
    }
};

class Solution {
public:
    _heap pq;
    int minOperations(vector& nums, int k) {
        for(int i = 0 ; i < nums.size(); i++){
            pq.push(nums[i]);
        }
        int cnt = 0;
        while(!pq.empty()){
            long long x = pq.pop();
            if (x >= k) break;
            long long y = pq.pop();
            pq.push(min(x, y)*2 + max(x, y));
            cnt++;
        }
        return cnt;
    }
};

Leetcode Problem:

• Divide Players Into Teams of Equal Skill

Summary

• Divide players into teams of equal skill and return the sum of chemistry of all teams.

Approach

• Use a hash map to store the frequency of each skill, sort the skills, and then iterate over the sorted skills to divide the players into teams.

Complexity

• O(n log n) due to sorting, where n is the number of players

Explain

• The solution first calculates the total skill and the target skill for each team
• It then iterates over the sorted skills, and for each skill, it checks if there is a corresponding team with the required skill
• If found, the players are divided into the team and the chemistry is calculated and added to the result
• If not found, the function returns -1.

Solution Code:

class Solution {
public:
    long long dividePlayers(vector& skill) {
        unordered_map m;
        sort(skill.begin(), skill.end());
        int total = 0;
        int N = skill.size();
        for(int i = 0 ; i < N; i++){
            m[skill[i]]++;
            total += skill[i];
        }
        int eachSum = total / (N / 2);
        long long res = 0;
        for(int i = 0 ; i < N/2; i++){
            int a = skill[i];
            int b = eachSum - a;
            if (m[a] == 0) return -1;
            m[a]--;
            if (m[b] == 0) return -1;
            m[b]--;
            res += a*b;
        }
        return res;

    }
};

Leetcode Problem:

• Make Sum Divisible by P

Summary

• Given an array of positive integers and a divisor, find the length of the smallest subarray that needs to be removed to make the sum of the remaining elements divisible by the divisor.

Approach

• The solution uses a sliding window approach and a hash map to keep track of the prefix sum modulo the divisor
• It iterates through the array, updating the prefix sum and the hash map, and at each step, it checks if there is a previous prefix sum that is congruent to the current prefix sum minus the needed prefix sum modulo the divisor
• If such a prefix sum exists, it updates the result with the minimum length of the subarray that needs to be removed.

Complexity

• O(n), where n is the length of the array, because each element in the array is processed once.

Explain

• The solution starts by initializing the result with the length of the array, the needed prefix sum, and the current prefix sum
• It then iterates through the array, updating the current prefix sum and the hash map
• At each step, it checks if there is a previous prefix sum that is congruent to the current prefix sum minus the needed prefix sum modulo the divisor
• If such a prefix sum exists, it updates the result with the minimum length of the subarray that needs to be removed
• Finally, it returns the result, which is either the minimum length of the subarray that needs to be removed or -1 if it is impossible to make the sum of the remaining elements divisible by the divisor.

Solution Code:

class Solution {
public:
    
      int minSubarray(vector& A, int p) {
        int n = A.size(), res = n, need = 0, cur = 0;
        for (auto a : A)
            need = (need + a) % p;
        unordered_map last = {{0, -1}};
        for (int i = 0; i < n; ++i) {
            cur = (cur + A[i]) % p;
            last[cur] = i;
            int want = (cur - need + p) % p;
            if (last.count(want))
                res = min(res, i - last[want]);
        }
        return res < n ? res : -1;
    }
};

Leetcode Problem:

• Rank Transform of an Array

Summary

• Given an array of integers, replace each element with its rank
• The rank represents how large the element is.

Approach

• The approach used is to first sort the array and then create a map to store the rank of each unique number
• Then, for each number in the original array, find its rank in the map and add it to the result vector.

Complexity

• O(n log n) due to the sorting step, where n is the number of elements in the array.

Solution Code:

class Solution {
public:
    vector arrayRankTransform(vector& arr) {
        vector arr2 = arr;
        sort(arr2.begin(), arr2.end());
        unordered_map m;
        
        int rank = 0;
        int curNum = -1;
        for(int num : arr2){
            if(curNum == num){
                continue;
            }
            curNum = num;
            rank++;
            m[num] = rank;
        }

        vector ans;
        for(int num: arr){
            ans.push_back(m[num]);
        }
        return ans;
    }
};

Leetcode Problem:

• Check If Array Pairs Are Divisible by k

Summary

• Given an array of integers and an integer k, determine if it is possible to divide the array into exactly n/2 pairs such that the sum of each pair is divisible by k.

Approach

• This problem can be solved using a hash map to count the remainders of the array elements when divided by k
• We first calculate the offset as k * k, then for each number in the array, we increment the count of the remainder
• If the count of 0 is odd, it means that we cannot divide the array into pairs with sum divisible by k
• Otherwise, we check if the counts of all remainders from 1 to k-1 are equal, and if the count of k/2 is odd when k is even
• If any of these conditions are not met, we return false
• Otherwise, we return true.

Complexity

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

Explain

• This solution works by first calculating the offset as k * k, then for each number in the array, we increment the count of the remainder
• If the count of 0 is odd, it means that we cannot divide the array into pairs with sum divisible by k
• Otherwise, we check if the counts of all remainders from 1 to k-1 are equal, and if the count of k/2 is odd when k is even
• If any of these conditions are not met, we return false
• Otherwise, we return true.

Solution Code:

class Solution {
public:
    unordered_map cnt;
    bool canArrange(vector& arr, int k) {
        if (k == 1) return true;
        long long offset = k;
        while(offset < 1e9){
            offset *= k;
        }
        for(long long num : arr){
            cnt[(num + offset) % k]++;
        }
        if(cnt[0] & 1) return false;
        for(int i = 1; i < ((k+1)>>1); i++){
            if(cnt[i] != cnt[k - i]) return false;
        }
        if((k %2) == 0 && ((cnt[k/2] %2) == 1)){
            return false;
        }
        return true;
    }
};