짬뽕얼큰하게의 맨땅에 헤딩 :: 'Algorithm' 태그의 글 목록 (6 Page)

String Matching in an Array

알고리즘 2025. 3. 4. 08:44

Leetcode Problem:

Summary

  • Given an array of strings, return all strings that are a substring of another word.

Approach

  • The solution iterates over each word in the input array and checks if it is a substring of any other word in the array
  • It uses nested loops to compare characters between words.

Complexity

  • O(n^3) where n is the number of words in the input array

Explanation

  • The solution iterates over each word in the input array and checks if it is a substring of any other word in the array
  • It uses nested loops to compare characters between words
  • The outer loop iterates over each word, the middle loop checks if the current word is a substring of any other word, and the inner loop compares characters between words
  • If a word is found to be a substring of another word, it is added to the result array and the middle loop is terminated to avoid unnecessary comparisons.

Solution Code:


class Solution {
public:
    vector stringMatching(vector& words) {
        vector ans;
        for(int i = 0 ; i < words.size(); i++){
            bool success = false;
            for(int j = 0; j < words.size(); j++){
                if(i == j) continue;
                for(int k = 0; k < words[j].size(); k++){
                    int l = 0;
                    for(; l < words[i].size(); l++){
                        if(words[j][k+l] != words[i][l]) break;
                    }
                    if(l == words[i].size()){
                        ans.push_back(words[i]);
                        success = true;
                        break;
                    }
                }
                if(success) break;
            }
        }
        return ans;
    }
};

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

Counting Words With a Given Prefix  (0) 2025.03.04
Count Prefix and Suffix Pairs I  (0) 2025.03.04
Minimum Number of Operations to Move All Balls to Each Box  (0) 2025.03.04
Shifting Letters II  (0) 2025.03.04
Partition Array According to Given Pivot  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Minimum Number of Operations to Move All Balls to Each Box

알고리즘 2025. 3. 4. 08:41

Leetcode Problem:

Summary

  • Given a binary string representing boxes with balls, find the minimum number of operations needed to move all the balls to each box.

Approach

  • The approach is to first count the number of balls in each box and store it in the `ltor` and `rtol` arrays
  • Then, calculate the minimum number of operations needed to move all the balls to each box by adding the `ltor` and `rtol` values at each index.

Complexity

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

Explanation

  • The provided C++ solution uses two arrays, `ltor` and `rtol`, to store the cumulative count of balls from the left and right sides of each box
  • The minimum number of operations needed to move all the balls to each box is calculated by adding the `ltor` and `rtol` values at each index
  • This approach ensures that the minimum number of operations is calculated considering the initial state of the boxes.

Solution Code:


class Solution {
public:
    int ltor[2000];
    int rtol[2000];
    vector minOperations(string boxes) {
        vector ans;
        int oneCnt = 0;
        for(int i = 0 ; i < boxes.size() - 1; i++){
            if(boxes[i] == '1'){
                oneCnt++;
            }
            ltor[i+1] = ltor[i] + oneCnt;
        }
        oneCnt = 0;
        for(int i = boxes.size() - 1; i > 0 ; i--){
            if(boxes[i] == '1'){
                oneCnt++;
            }
            rtol[i-1] = rtol[i] + oneCnt;
        }
        for(int i = 0 ; i < boxes.size(); i++){
            ans.push_back(ltor[i] + rtol[i]);
        }
        return ans;
    }
};

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

Count Prefix and Suffix Pairs I  (0) 2025.03.04
String Matching in an Array  (0) 2025.03.04
Shifting Letters II  (0) 2025.03.04
Partition Array According to Given Pivot  (0) 2025.03.03
Number of Ways to Split Array  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

Shifting Letters II

알고리즘 2025. 3. 4. 08:38

Leetcode Problem:

Summary

  • Given a string s and a 2D integer array shifts, shift the characters in s from the start index to the end index forward if direction is 1, or backward if direction is 0.

Approach

  • This solution uses a prefix sum array to efficiently calculate the cumulative sum of shifts for each character
  • It then iterates over the string, adding the prefix sum to the current character's ASCII value and taking the modulus 26 to wrap around the alphabet.

Complexity

  • O(n + m) where n is the length of the string s and m is the number of shifts, as it needs to iterate over the string and the shifts array once.

Explanation

  • The prefix sum array pSum is used to store the cumulative sum of shifts for each character
  • For each shift, the sum of the character at the start index and the sum of the character at the end index plus the shift direction are added to pSum[start] and pSum[end+1] respectively
  • Then, the string is iterated over, and the prefix sum is added to the current character's ASCII value to get the shifted character
  • The modulus 26 is taken to wrap around the alphabet.

Solution Code:


class Solution {
public:
    int pSum[500001];
    int fb[2] = {25, 1};
    string shiftingLetters(string s, vector>& shifts) {
        for(int i = 0 ; i < shifts.size(); i++){
            int start = shifts[i][0];
            int end = shifts[i][1];
            int dir = shifts[i][2];
            pSum[start] += fb[dir];
            pSum[start] %= 26;
            pSum[end+1] += fb[dir ^ 1];
            pSum[end+1] %= 26;
            
        }

        string ans = "";
        for(int i = 0 ; i < s.size(); i++){
            pSum[i+1] += pSum[i];
            pSum[i] %= 26;
            unsigned char c = s[i] + pSum[i];
            if(c > 'z') c = 'a' + (c - 'z') - 1;
            if(c < 'a') c = 'z' - ('a' - c - 1);
            ans += c;
        }
        
        return ans;
    }
};

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

String Matching in an Array  (0) 2025.03.04
Minimum Number of Operations to Move All Balls to Each Box  (0) 2025.03.04
Partition Array According to Given Pivot  (0) 2025.03.03
Number of Ways to Split Array  (0) 2025.03.03
Count Vowel Strings in Ranges  (0) 2025.03.03
블로그 이미지

짬뽕얼큰하게

,

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

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   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

티스토리툴바