짬뽕얼큰하게의 맨땅에 헤딩 :: '분류 전체보기' 카테고리의 글 목록 (6 Page)

Partition Array According to Given Pivot

알고리즘 2025. 3. 3. 12:50

Leetcode Problem:

Summary

  • Given an array of integers and a pivot value, rearrange the array such that all elements less than the pivot appear before all elements greater than the pivot, and elements equal to the pivot appear in between.

Approach

  • Separate the array into three lists: less than pivot, equal to pivot, and greater than pivot
  • Then, concatenate these lists to form the rearranged array.

Complexity

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

Explanation

  • This solution uses three lists to separate the array into three categories based on the pivot value
  • Then, it concatenates these lists to form the rearranged array
  • This approach ensures that all elements less than the pivot appear before all elements greater than the pivot, and elements equal to the pivot appear in between
  • The time complexity is O(n) because each element in the array is visited once.

Solution Code:


class Solution {
public:
    vector pivotArray(vector& nums, int pivot) {
        vector less;
        vector equal;
        vector greater;
        for(int i = 0 ; i < nums.size(); i++){
            if(nums[i] < pivot){
                less.push_back(nums[i]);
            } else if(nums[i] > pivot){
                greater.push_back(nums[i]);
            } else{
                equal.push_back(nums[i]);
            }
        }
        vector ans;
        ans.insert(ans.end(), less.begin(), less.end());
        ans.insert(ans.end(), equal.begin(), equal.end());
        ans.insert(ans.end(), greater.begin(), greater.end());
        return ans;
    }
};

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

Minimum Number of Operations to Move All Balls to Each Box  (0) 2025.03.04
Shifting Letters II  (0) 2025.03.04
Number of Ways to Split Array  (0) 2025.03.03
Count Vowel Strings in Ranges  (0) 2025.03.03
Minimum Cost For Tickets  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Number of Ways to Split Array

알고리즘 2025. 3. 3. 09:07

Leetcode Problem:

Summary

  • The problem requires to find the number of valid splits in the given array
  • A valid split is when the sum of the first i+1 elements is greater than or equal to the sum of the last n-i-1 elements.

Approach

  • The approach used is to calculate the prefix sum of the array and then iterate over the array to check for valid splits
  • The prefix sum is calculated using a dynamic programming approach and stored in an array
  • Then, for each index i, the sum of the first i+1 elements is compared with the sum of the last n-i-1 elements
  • If the sum of the first i+1 elements is greater than or equal to the sum of the last n-i-1 elements, then the index i is considered as a valid split.

Complexity

  • O(n)

Explanation

  • The time complexity of the solution is O(n) because we are iterating over the array once to calculate the prefix sum and again to check for valid splits
  • The space complexity is also O(n) because we are storing the prefix sum in an array of size n.

Solution Code:


class Solution {
public:
    long long pSum[100000];
    int waysToSplitArray(vector& nums) {
        pSum[0] = nums[0];
        for(int i = 1 ; i < nums.size(); i++){
            pSum[i] = pSum[i-1] + nums[i];
        }
        int ans = 0;
        int last = nums.size() - 1;
        for(int i = 0; i < last; i++){
            if(pSum[i] >= pSum[last] - pSum[i]){
                ans++;
            }
        }
        return ans;
    }
};

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

Shifting Letters II  (0) 2025.03.04
Partition Array According to Given Pivot  (0) 2025.03.03
Count Vowel Strings in Ranges  (0) 2025.03.03
Minimum Cost For Tickets  (0) 2025.03.03
Count Ways To Build Good Strings  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Count Vowel Strings in Ranges

알고리즘 2025. 3. 3. 09:04

Leetcode Problem:

Summary

  • Given a list of strings and queries, find the number of strings that start and end with a vowel.

Approach

  • Use a prefix sum array to store the count of strings that start and end with a vowel
  • Then, for each query, subtract the count of strings that start at the query's left index from the count of strings that end at the query's right index.

Complexity

  • O(n + m * q) where n is the number of strings, m is the maximum length of a string, and q is the number of queries.

Explanation

  • The prefix sum array is initialized with all zeros
  • Then, for each string, if the first and last characters are both vowels, increment the count at that index
  • Finally, for each query, subtract the count at the left index from the count at the right index to get the answer.

Solution Code:


class Solution {
public:
    int pSum[100002];

    bool isVowel(char c){
        if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'){
            return true;
        }
        return false;
    }
    vector vowelStrings(vector& words, vector>& queries) {
        for(int i = 0 ; i < words.size(); i++){
            pSum[i+1] = pSum[i];
            string s = words[i];
            if(isVowel(s[0]) && isVowel(s[s.size() - 1])){
                pSum[i+1]++;
            }
        }
        vector ans;
        for(int i = 0 ; i < queries.size(); i++){
            ans.push_back(pSum[queries[i][1]+1] - pSum[queries[i][0]]);
        }
        return ans;
    }
};

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

Partition Array According to Given Pivot  (0) 2025.03.03
Number of Ways to Split Array  (0) 2025.03.03
Minimum Cost For Tickets  (0) 2025.03.03
Count Ways To Build Good Strings  (0) 2025.03.03
Number of Ways to Form a Target String Given a Dictionary  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Minimum Cost For Tickets

알고리즘 2025. 3. 3. 09:00

Leetcode Problem:

Summary

  • The problem is to find the minimum cost of traveling a list of days given the costs of 1-day, 7-day, and 30-day passes.

Approach

  • Dynamic programming is used to solve this problem
  • The idea is to create a dp array where dp[i] represents the minimum cost to reach day i
  • The dp array is initialized with zeros and then filled up in a bottom-up manner
  • For each day, if the day is less than the current day in the days array, the cost is the same as the previous day
  • Otherwise, the cost is the minimum of the cost of buying a 1-day pass, a 7-day pass, and a 30-day pass for the current day.

Complexity

  • O(n) where n is the number of days.

Explanation

  • The dynamic programming approach is used to solve this problem efficiently
  • The dp array is filled up in a bottom-up manner, starting from day 1
  • For each day, if the day is less than the current day in the days array, the cost is the same as the previous day
  • Otherwise, the cost is the minimum of the cost of buying a 1-day pass, a 7-day pass, and a 30-day pass for the current day
  • This approach avoids the need to calculate the cost for each day multiple times, making it more efficient.

Solution Code:


class Solution {
public:
    int mincostTickets(vector& days, vector& costs) {
        int lastDay = days[days.size() - 1];
        vector dp(lastDay + 1, 0);
        
        int i = 0;
        for (int day = 1; day <= lastDay; day++) {
            if (day < days[i]) {
                dp[day] = dp[day - 1];
            } else {
                i++;
                dp[day] = min({dp[day - 1] + costs[0],
                               dp[max(0, day - 7)] + costs[1],
                               dp[max(0, day - 30)] + costs[2]});
            }
        }
     
        return dp[lastDay];
    }
};

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

Number of Ways to Split Array  (0) 2025.03.03
Count Vowel Strings in Ranges  (0) 2025.03.03
Count Ways To Build Good Strings  (0) 2025.03.03
Number of Ways to Form a Target String Given a Dictionary  (0) 2025.03.03
Maximum Sum of 3 Non-Overlapping Subarrays  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Count Ways To Build Good Strings

알고리즘 2025. 3. 3. 08:57

Leetcode Problem:

Summary

  • Find the number of different good strings that can be constructed satisfying the given properties.

Approach

  • This problem can be solved using dynamic programming
  • We use a memoization table to store the results of subproblems and avoid redundant computation.

Complexity

  • O(n * zero * one), where n is the range of possible lengths (high - low + 1)

Explanation

  • The `getCnt` function calculates the number of good strings of a given length that can be constructed using the given number of zeros and ones
  • It uses memoization to store the results of subproblems and avoid redundant computation
  • The `countGoodStrings` function iterates over the range of possible lengths and calls `getCnt` to calculate the total number of good strings
  • The result is then taken modulo 10^9 + 7 to avoid overflow.

Solution Code:


#define MOD 1000000007
class Solution {
public:
    int memo[100001];
    long long getCnt(int length, int zero, int one){
        if(length < 0) return 0;
        if(length == 0){
            return 1;
        }
        if(memo[length] != -1) return memo[length];
        long long ret = 0;
        ret += getCnt(length - zero, zero, one);
        ret %= MOD;
        ret += getCnt(length - one , zero, one);
        ret %= MOD;
        return memo[length] = ret;
    }
    int countGoodStrings(int low, int high, int zero, int one) {
        memset(memo, -1, sizeof(memo));
        long long ans = 0;
        for(int i = low; i <= high; i++){
            ans += getCnt(i, zero, one);
            ans %= MOD;
        }
        return ans;
    }
};

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

Count Vowel Strings in Ranges  (0) 2025.03.03
Minimum Cost For Tickets  (0) 2025.03.03
Number of Ways to Form a Target String Given a Dictionary  (0) 2025.03.03
Maximum Sum of 3 Non-Overlapping Subarrays  (0) 2025.03.03
Best Sightseeing Pair  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Number of Ways to Form a Target String Given a Dictionary

알고리즘 2025. 3. 3. 08:54

Leetcode Problem:

Summary

  • This is a problem of forming a target string using given words with certain restrictions.

Approach

  • Dynamic programming is used to solve this problem
  • The approach involves creating a dictionary to store the frequency of each character in each word and a memoization table to store the intermediate results.

Complexity

  • O(n*m*d) where n is the length of the target string, m is the number of words, and d is the number of unique characters in the words.

Explanation

  • The solution starts by initializing a dictionary to store the frequency of each character in each word and a memoization table to store the intermediate results
  • It then iterates over each word and character in the target string, using the dictionary to get the frequency of the current character and the memoization table to store the intermediate results
  • The final result is obtained by summing up the number of ways to form the target string using each word and character.

Solution Code:


class Solution {
public:
    int dict[1001][128];
    int memo[1001][1001];
    int dictN;
    long long getCnt(string& target, int targetIdx, int dictIdx){
        if(target.size() == targetIdx) return 1;
        if(dictIdx >= dictN) return 0;
        if(memo[dictIdx][targetIdx] != -1) return memo[dictIdx][targetIdx];
        long long ret = 0;
        for(int i = dictIdx; i < dictN - (target.size() - targetIdx - 1); i++){
            if(dict[i][target[targetIdx]] == 0) continue;
            ret += getCnt(target, targetIdx+1, i + 1) * dict[i][target[targetIdx]] % 1000000007;
            ret %= 1000000007;
        }
        return memo[dictIdx][targetIdx] = ret;
    }
    int numWays(vector& words, string target) {
        dictN = words[0].size();
        memset(memo, -1, sizeof(memo));
        if(dictN < target.size()) return 0;
        for(int i = 0 ; i < words.size(); i++){
            for(int j = 0 ; j < dictN; j++){
                dict[j][words[i][j]]++;
            }
        }
        return getCnt(target, 0, 0);
    }
};

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

Minimum Cost For Tickets  (0) 2025.03.03
Count Ways To Build Good Strings  (0) 2025.03.03
Maximum Sum of 3 Non-Overlapping Subarrays  (0) 2025.03.03
Best Sightseeing Pair  (0) 2025.03.03
Target Sum  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Maximum Sum of 3 Non-Overlapping Subarrays

알고리즘 2025. 3. 3. 08:50

Leetcode Problem:

Summary

  • Given an integer array and an integer k, find three non-overlapping subarrays of length k with maximum sum and return their starting indices.

Approach

  • Dynamic programming and depth-first search are used to find the maximum possible sum of subarrays and then reconstruct the path to find the starting indices.

Complexity

  • O(n * 4^k) where n is the size of the input array, as the dynamic programming function is called for each possible subarray and for each possible number of subarrays remaining.

Explanation

  • The solution first calculates the sum of all possible k-length subarrays using a sliding window approach
  • Then, it uses dynamic programming to find the maximum possible sum of subarrays
  • The dynamic programming function tries taking the current subarray vs skipping it and returns the maximum result
  • Finally, the solution uses depth-first search to reconstruct the path to find the starting indices of the subarrays.

Solution Code:


class Solution {
public:
    vector maxSumOfThreeSubarrays(vector& nums, int k) {
        // Number of possible subarray starting positions
        int n = nums.size() - k + 1;

        // Calculate sum of all possible k-length subarrays
        vector sums(n);
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }
        sums[0] = windowSum;

        // Sliding window to calculate remaining sums
        for (int i = k; i < nums.size(); i++) {
            windowSum = windowSum - nums[i - k] + nums[i];
            sums[i - k + 1] = windowSum;
        }

        // memo[i][j]: max sum possible starting from index i with j subarrays
        // remaining
        vector> memo(n, vector(4, -1));
        vector indices;

        // First find optimal sum using DP
        dp(sums, k, 0, 3, memo);

        // Then reconstruct the path to find indices
        dfs(sums, k, 0, 3, memo, indices);

        return indices;
    }

private:
    // DP function to find maximum possible sum
    int dp(vector& sums, int k, int idx, int rem,
           vector>& memo) {
        if (rem == 0) return 0;
        if (idx >= sums.size()) {
            return rem > 0 ? INT_MIN : 0;
        }

        if (memo[idx][rem] != -1) {
            return memo[idx][rem];
        }

        // Try taking current subarray vs skipping it
        int withCurrent = sums[idx] + dp(sums, k, idx + k, rem - 1, memo);
        int skipCurrent = dp(sums, k, idx + 1, rem, memo);

        memo[idx][rem] = max(withCurrent, skipCurrent);
        return memo[idx][rem];
    }

    // DFS to reconstruct the solution path
    void dfs(vector& sums, int k, int idx, int rem,
             vector>& memo, vector& indices) {
        if (rem == 0) return;
        if (idx >= sums.size()) return;

        int withCurrent = sums[idx] + dp(sums, k, idx + k, rem - 1, memo);
        int skipCurrent = dp(sums, k, idx + 1, rem, memo);

        // Choose path that gave optimal result in DP
        if (withCurrent >= skipCurrent) {  // Take current subarray
            indices.push_back(idx);
            dfs(sums, k, idx + k, rem - 1, memo, indices);
        } else {  // Skip current subarray
            dfs(sums, k, idx + 1, rem, memo, indices);
        }
    }
};

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

Count Ways To Build Good Strings  (0) 2025.03.03
Number of Ways to Form a Target String Given a Dictionary  (0) 2025.03.03
Best Sightseeing Pair  (0) 2025.03.03
Target Sum  (0) 2025.03.03
Find Largest Value in Each Tree Row  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Best Sightseeing Pair

알고리즘 2025. 3. 3. 08:46

Leetcode Problem:

Summary

  • Given an array of sightseeing spot values, find the maximum score of a pair of sightseeing spots.

Approach

  • This problem can be solved using dynamic programming
  • We maintain two arrays: maxLeftScore and maxRightScore
  • maxLeftScore[i] represents the maximum score of a sightseeing spot at index i from the left, and maxRightScore[i] represents the maximum score of a sightseeing spot at index i from the right
  • We update these arrays iteratively, and the maximum score is the maximum of the sum of maxLeftScore[i-1] and maxRightScore[i], or maxLeftScore[i-1] plus the current right score.

Complexity

  • O(n)

Explanation

  • The time complexity is O(n) because we are iterating through the array once
  • The space complexity is O(n) because we are storing the maximum left and right scores for each index.

Solution Code:


class Solution {
public:
    int maxScoreSightseeingPair(vector& values) {
        int n = values.size();
        // Initialize an array to store the maximum left scores up to each
        // index.
        vector maxLeftScore(n);
        // The left score at the first index is just the value of the first
        // element.
        maxLeftScore[0] = values[0];

        int maxScore = 0;

        for (int i = 1; i < n; i++) {
            int currentRightScore = values[i] - i;
            // Update the maximum score by combining the best left score so far
            // with the current right score.
            maxScore = max(maxScore, maxLeftScore[i - 1] + currentRightScore);

            int currentLeftScore = values[i] + i;
            // Update the maximum left score up to the current index.
            maxLeftScore[i] = max(maxLeftScore[i - 1], currentLeftScore);
        }

        return maxScore;
    }
};

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

Number of Ways to Form a Target String Given a Dictionary  (0) 2025.03.03
Maximum Sum of 3 Non-Overlapping Subarrays  (0) 2025.03.03
Target Sum  (0) 2025.03.03
Find Largest Value in Each Tree Row  (0) 2025.03.03
Minimum Number of Operations to Sort a Binary Tree by Level  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Target Sum

알고리즘 2025. 3. 3. 08:43

Leetcode Problem:

Summary

  • Find the number of different expressions that can be built from the given integer array and target sum.

Approach

  • Dynamic programming with memoization
  • The function recursively tries all possible combinations of '+' and '-' operations before the current number and stores the results in a memoization table to avoid redundant calculations.

Complexity

  • O(n * sum), where n is the length of the input array and sum is the target sum.

Explanation

  • The solution uses a recursive function with memoization to try all possible combinations of '+' and '-' operations before the current number
  • The memoization table stores the results of subproblems to avoid redundant calculations
  • The base cases are when the current index is 0 (no more numbers to process) or when the sum equals the target
  • The function returns 1 if the sum equals the target and 0 otherwise
  • The results are stored in the memoization table and returned.

Solution Code:


class Solution {
public:
    int memo[20][2001];
    int findTargetSumWays(vector& nums, int target, int cur=0, int sum=0) {
        if(cur == 0){
            memset(memo, -1, sizeof(memo));
        }
        if(cur == nums.size()){
            if (sum == target){
                return 1;
            }
            return 0;
        }
        if(memo[cur][sum+1000] != -1) return memo[cur][sum+1000];
        int res = 0;
        res += findTargetSumWays(nums, target, cur+1, sum + nums[cur]);
        res += findTargetSumWays(nums, target, cur+1, sum - nums[cur]);
        return memo[cur][sum+1000] = res;
    }
};

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

Maximum Sum of 3 Non-Overlapping Subarrays  (0) 2025.03.03
Best Sightseeing Pair  (0) 2025.03.03
Find Largest Value in Each Tree Row  (0) 2025.03.03
Minimum Number of Operations to Sort a Binary Tree by Level  (0) 2025.03.03
Merge Two 2D Arrays by Summing Values  (0) 2025.03.02
블로그 이미지

짬뽕얼큰하게

,

Find Largest Value in Each Tree Row

알고리즘 2025. 3. 3. 08:40

Leetcode Problem:

Summary

  • Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Approach

  • The solution uses a level order traversal (BFS) approach with a depth-first traversal (DFS) to find the largest value in each row
  • It uses a queue to store the nodes at each level and a vector to store the largest values.

Complexity

  • O(n), where n is the number of nodes in the tree
  • Each node is visited once.

Explanation

  • The solution starts by initializing a vector to store the largest values and a queue to store the nodes at each level
  • It then performs a level order traversal of the tree using a BFS approach
  • At each level, it finds the maximum value and stores it in the vector
  • The traversal is done using a DFS approach by recursively visiting the left and right children of each node
  • The time complexity is O(n) because each node is visited once, and the space complexity is O(n) because the queue stores the nodes at each level.

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:
    vector ans;
    void traversal(TreeNode* root, int depth){
        if(root == nullptr) return;
        if(ans.size() == depth){
            ans.push_back(root->val);
        } else{
            ans[depth] = max(ans[depth], root->val);
        }
        traversal(root->left, depth + 1);
        traversal(root->right, depth + 1);
    }
    vector largestValues(TreeNode* root) {
        traversal(root, 0);
        return ans;
    }
};

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

Best Sightseeing Pair  (0) 2025.03.03
Target Sum  (0) 2025.03.03
Minimum Number of Operations to Sort a Binary Tree by Level  (0) 2025.03.03
Merge Two 2D Arrays by Summing Values  (0) 2025.03.02
Apply Operations to an Array  (0) 2025.03.01
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

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

티스토리툴바