짬뽕얼큰하게의 맨땅에 헤딩 :: '알고리즘' 태그의 글 목록 (2 Page)

Build Array from Permutation

알고리즘 2025. 5. 6. 23:14

Leetcode Problem:

Summary

  • Given a zero-based permutation, build an array where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it.

Approach

  • This solution uses a simple iterative approach where it iterates over the input array and uses the value at each index as the index for the next value in the output array.

Complexity

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

Explanation

  • The solution uses a vector to store the output array and iterates over the input array
  • For each index in the input array, it uses the value at that index as the index for the next value in the output array
  • This approach is simple and efficient, with a time complexity of O(n) where n is the length of the input array.

Solution Code:


class Solution {
public:
    vector ans;
    vector buildArray(vector& nums) {
        for(int i = 0 ; i < nums.size(); i++){
            ans.push_back(nums[nums[i]]);
        }
        return ans;
    }
};

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

Find Minimum Time to Reach Last Room II  (1) 2025.05.08
Find Minimum Time to Reach Last Room I  (0) 2025.05.07
Domino and Tromino Tiling  (1) 2025.05.05
Number of Equivalent Domino Pairs  (0) 2025.05.04
Minimum Domino Rotations For Equal Row  (1) 2025.05.03
블로그 이미지

짬뽕얼큰하게

,

Domino and Tromino Tiling

알고리즘 2025. 5. 5. 11:33

Leetcode Problem:

Summary

  • The problem requires finding the number of ways to tile a 2 x n board with 2 x 1 dominoes and a tromino shape, with the answer being modulo 10^9 + 7.

Approach

  • The solution uses dynamic programming to calculate the number of ways to tile the board
  • It initializes an array `memo` to store the number of ways to tile a board of length `i`, and then iterates from `i = 4` to `n` to calculate the number of ways to tile a board of length `i`
  • For each `i`, it calculates the number of ways to tile a board of length `i` by considering the number of ways to tile a board of length `i-1` and `i-2`, and adds the number of ways to tile a board of length `i-3` to the result, taking into account the modulo operation to avoid overflow.

Complexity

  • O(n)

Explanation

  • The solution uses a dynamic programming approach to calculate the number of ways to tile the board
  • It initializes an array `memo` to store the number of ways to tile a board of length `i`, and then iterates from `i = 4` to `n` to calculate the number of ways to tile a board of length `i`
  • For each `i`, it calculates the number of ways to tile a board of length `i` by considering the number of ways to tile a board of length `i-1` and `i-2`, and adds the number of ways to tile a board of length `i-3` to the result, taking into account the modulo operation to avoid overflow
  • The time complexity of the solution is O(n) because it iterates from `i = 4` to `n` once, and the space complexity is O(n) because it stores the number of ways to tile a board of length `i` in the `memo` array.

Solution Code:


#define MOD 1000000007
class Solution {
public:
    int memo[1001];
    int numTilings(int n) {
        memo[0] = 1;
        memo[1] = 1;
        memo[2] = 2;
        memo[3] = 5;
        for(int i = 4; i <= n; i++){
            memo[i] = (memo[i-1] + memo[i-2])%MOD;
            for(int j = i - 3; j >= 0; j--){
                memo[i] += (memo[j]*2)%MOD;
                memo[i] %= MOD;
            }
        }
        return memo[n];
    }
};

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

Find Minimum Time to Reach Last Room I  (0) 2025.05.07
Build Array from Permutation  (2) 2025.05.06
Number of Equivalent Domino Pairs  (0) 2025.05.04
Minimum Domino Rotations For Equal Row  (1) 2025.05.03
Push Dominoes  (2) 2025.05.02
블로그 이미지

짬뽕얼큰하게

,

Number of Equivalent Domino Pairs

알고리즘 2025. 5. 4. 09:25

Leetcode Problem:

Summary

  • Given a list of dominoes, find the number of pairs where one domino can be rotated to be equal to another domino.

Approach

  • The approach used is to first count the occurrences of each domino, then calculate the number of pairs by summing up the combinations of each domino, considering that each pair can be represented by two dominoes.

Complexity

  • O(n log n) due to sorting, where n is the number of dominoes, and O(1) for the space complexity where n is the maximum possible value of a domino.

Explanation

  • The solution works by first creating a hashmap to store the occurrences of each domino
  • Then it iterates over the hashmap and calculates the number of pairs for each domino by summing up the combinations of each domino, considering that each pair can be represented by two dominoes
  • The time complexity is O(n log n) due to sorting, and the space complexity is O(1) for the hashmap.

Solution Code:


class Solution {
public:
    unordered_map cnt;
    int numEquivDominoPairs(vector>& dominoes) {
        for(int i = 0 ; i < dominoes.size() ; i++){
            int a = dominoes[i][0];
            int b = dominoes[i][1];
            if(a > b){
                int t = a;
                a = b;
                b = t;
            }
            cnt[a*10 + b]++;
        }
        int ans = 0;
        for(auto iter = cnt.begin(); iter != cnt.end(); iter++){
            ans += (iter->second * (iter->second-1)) / 2;
        }
        return ans;
    }
};

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

Build Array from Permutation  (2) 2025.05.06
Domino and Tromino Tiling  (1) 2025.05.05
Minimum Domino Rotations For Equal Row  (1) 2025.05.03
Push Dominoes  (2) 2025.05.02
Maximum Number of Tasks You Can Assign  (1) 2025.05.01
블로그 이미지

짬뽕얼큰하게

,

Minimum Domino Rotations For Equal Row

알고리즘 2025. 5. 3. 21:23

Leetcode Problem:

Summary

  • The problem is to find the minimum number of rotations required to make all values in the tops or bottoms array equal
  • The function takes two arrays, tops and bottoms, as input and returns the minimum number of rotations
  • If it's not possible to make all values equal, the function returns -1.

Approach

  • The solution code uses a two-pass approach
  • First, it checks if it's possible to make all values in the tops or bottoms array equal by checking if there's a common value between the two arrays
  • If it's not possible, the function returns -1
  • Otherwise, it counts the number of rotations required to make all values in the tops or bottoms array equal.

Complexity

  • O(n), where n is the length of the tops and bottoms arrays
  • The function makes two passes through the arrays, one for each possible common value.

Explanation

  • The solution code first checks if it's possible to make all values in the tops or bottoms array equal by checking if there's a common value between the two arrays
  • If it's not possible, the function returns -1
  • Otherwise, it counts the number of rotations required to make all values in the tops or bottoms array equal
  • The function uses two counters, cnt1 and cnt2, to count the number of rotations required to make all values in the tops and bottoms arrays equal, respectively
  • The function returns the minimum of cnt1 and cnt2.

Solution Code:


class Solution {
public:
    int minDominoRotations(vector& tops, vector& bottoms) {
        int cur = tops[0];
        bool success = true;
        for(int i = 0 ; i < tops.size(); i++){
            if(tops[i] == cur || bottoms[i] == cur) continue;
            success = false;
            break;
        }
        if(!success){
            success = true;
            cur = bottoms[0];
            for(int i = 0 ; i < tops.size(); i++){
                if(tops[i] == cur || bottoms[i] == cur) continue;
                success = false;
                break;
            }
        }
        if(!success) return -1;

        int cnt1 = 0;
        int cnt2 = 0;
        for(int i = 0 ; i < tops.size(); i++){
            if(tops[i] != cur) cnt1++;
            if(bottoms[i] != cur) cnt2++;
        }
        return cnt1 < cnt2 ? cnt1 : cnt2;
    }
};

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

Domino and Tromino Tiling  (1) 2025.05.05
Number of Equivalent Domino Pairs  (0) 2025.05.04
Push Dominoes  (2) 2025.05.02
Maximum Number of Tasks You Can Assign  (1) 2025.05.01
Find Numbers with Even Number of Digits  (0) 2025.04.30
블로그 이미지

짬뽕얼큰하게

,

Push Dominoes

알고리즘 2025. 5. 2. 19:05

Leetcode Problem:

Summary

  • This problem is about simulating the movement of dominoes in a line
  • The dominoes can be pushed to the left or to the right, and they will move in the opposite direction if pushed from both sides.

Approach

  • The approach used in the solution is to iterate through the dominoes and for each domino, check if it has been pushed to the left or to the right
  • If it has been pushed to the left, all the dominoes to its left that have not been pushed will also be pushed to the left
  • If it has been pushed to the right, all the dominoes to its right that have not been pushed will be pushed to the right
  • If a domino has been pushed from both sides, it will stay still.

Complexity

  • O(n)

Explanation

  • The time complexity of the solution is O(n) because we are iterating through the dominoes once
  • The space complexity is O(1) because we are not using any extra space that scales with the input size.

Solution Code:


class Solution {
public:
    string pushDominoes(string dominoes) {
        for(int i = 0 ; i < dominoes.size(); i++){
            if(dominoes[i] == 'L'){
                int j = i-1;
                while(j >= 0 && dominoes[j] == '.'){
                    dominoes.at(j) = 'L';
                    j--;
                }
            } else if(dominoes[i] == 'R'){
                int j = i+1;
                while(j < dominoes.size() && dominoes[j] == '.'){
                    j++;
                }
                if(j >= dominoes.size() || dominoes[j] == 'R'){
                    for(; i < j; i++){
                        dominoes.at(i) = 'R';
                    }
                    if(j < dominoes.size() && dominoes[j] == 'R'){
                        i--;
                    }
                } else{
                    int k = i + 1;
                    int l = j - 1;
                    while(k < l){
                        dominoes.at(k) = 'R';
                        dominoes.at(l) = 'L';
                        k++;
                        l--;
                    }
                    i = j;
                }
            }
        }
        return dominoes;
    }
};

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

Number of Equivalent Domino Pairs  (0) 2025.05.04
Minimum Domino Rotations For Equal Row  (1) 2025.05.03
Maximum Number of Tasks You Can Assign  (1) 2025.05.01
Find Numbers with Even Number of Digits  (0) 2025.04.30
Count Subarrays Where Max Element Appears at Least K Times  (1) 2025.04.30
블로그 이미지

짬뽕얼큰하게

,

Maximum Number of Tasks You Can Assign

알고리즘 2025. 5. 1. 23:09

Leetcode Problem:

Summary

  • The problem requires to find the maximum number of tasks that can be completed with given tasks, workers, pills, and strength
  • Each task has a strength requirement, each worker has a strength, and there are magical pills that can increase a worker's strength.

Approach

  • The solution uses a binary search approach
  • It first sorts the tasks and workers arrays
  • Then, it performs a binary search between the minimum and maximum possible number of tasks that can be completed
  • In each iteration of the binary search, it checks if the current number of tasks can be completed by assigning the workers to the tasks
  • If it can, it moves the left pointer to the current number of tasks
  • Otherwise, it moves the right pointer to the previous number of tasks
  • Finally, it returns the left pointer as the maximum number of tasks that can be completed.

Complexity

  • The time complexity of the solution is O(n log n) due to the sorting of the tasks and workers arrays, where n is the number of tasks or workers
  • The space complexity is O(n) for the sorting of the tasks and workers arrays.

Explanation

  • The solution first sorts the tasks and workers arrays
  • Then, it performs a binary search between the minimum and maximum possible number of tasks that can be completed
  • In each iteration of the binary search, it checks if the current number of tasks can be completed by assigning the workers to the tasks
  • If it can, it moves the left pointer to the current number of tasks
  • Otherwise, it moves the right pointer to the previous number of tasks
  • Finally, it returns the left pointer as the maximum number of tasks that can be completed
  • The solution uses a multiset to keep track of the workers' strength after assigning the magical pills.

Solution Code:


class Solution {
public:
    int maxTaskAssign(vector& tasks, vector& workers, int pills, int strength) {
        int left = 0, right = min(tasks.size(), workers.size());

        sort(tasks.begin(), tasks.end());
        sort(workers.begin(), workers.end());

        while(left < right) {
            int mid = (left + right + 1) / 2;
            int usedPills = 0;
            multiset workersFree(workers.end() - mid, workers.end());

            bool canAssign = true;
            for(int i = mid - 1; i >= 0; --i) {
                auto it = prev(workersFree.end());

                if(*it < tasks[i]) {
                    it = workersFree.lower_bound(tasks[i] - strength);
                    if(it == workersFree.end()) {
                        canAssign = false;
                        break;
                    }
                    ++usedPills;
                    if(usedPills > pills) {
                        canAssign = false;
                        break;
                    }
                }
                workersFree.erase(it);
            }

            if(canAssign)
                left = mid;
            else
                right = mid - 1;
        }
        return left;
    }
};

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

Minimum Domino Rotations For Equal Row  (1) 2025.05.03
Push Dominoes  (2) 2025.05.02
Find Numbers with Even Number of Digits  (0) 2025.04.30
Count Subarrays Where Max Element Appears at Least K Times  (1) 2025.04.30
Count Subarrays of Length Three With a Condition  (1) 2025.04.27
블로그 이미지

짬뽕얼큰하게

,

Find Numbers with Even Number of Digits

알고리즘 2025. 4. 30. 20:31

Leetcode Problem:

Summary

  • Count numbers with even number of digits in an array

Approach

  • The approach used is to iterate through each number in the array and calculate the number of digits in each number using a helper function
  • If the number of digits is even, it increments the counter
  • Finally, it returns the count of numbers with even number of digits.

Complexity

  • O(n * log(max_num)) where n is the size of the array and max_num is the maximum number in the array

Explanation

  • The solution iterates through each number in the array
  • For each number, it calculates the number of digits using a helper function
  • If the number of digits is even, it increments the counter
  • The time complexity of the helper function is O(log(max_num)) and it is called for each number in the array
  • Therefore, the overall time complexity is O(n * log(max_num)) where n is the size of the array and max_num is the maximum number in the array.

Solution Code:


class Solution {
public:
    int getDigitNum(int num){
        int cnt = 0;
        while(num){
            num/=10;
            cnt++;
        }
        return cnt;
    }
    int findNumbers(vector& nums) {
        int ans = 0;
        for(int num : nums){
            if(getDigitNum(num) % 2){
                continue;
            }
            ans++;
        }
        return ans;
    }
};

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

Push Dominoes  (2) 2025.05.02
Maximum Number of Tasks You Can Assign  (1) 2025.05.01
Count Subarrays Where Max Element Appears at Least K Times  (1) 2025.04.30
Count Subarrays of Length Three With a Condition  (1) 2025.04.27
Count Subarrays With Fixed Bounds  (0) 2025.04.26
블로그 이미지

짬뽕얼큰하게

,

Count Subarrays Where Max Element Appears at Least K Times

알고리즘 2025. 4. 30. 00:46

Leetcode Problem:

Summary

  • The problem requires finding the number of subarrays in a given array where the maximum element appears at least k times.

Approach

  • The approach used is to first identify the maximum element and its corresponding subarray
  • Then, we iterate over the subarray and count the number of subarrays that contain the maximum element at least k times.

Complexity

  • O(n), where n is the size of the input array.

Explanation

  • The solution first creates a vector to store the indices of the maximum element in the subarray
  • It then iterates over the array to find the maximum element and its indices
  • After that, it calculates the number of subarrays that contain the maximum element at least k times by iterating over the vector and counting the subarrays.

Solution Code:


class Solution {
public:
    vector v;
    long long countSubarrays(vector& nums, int k) {
        int maxV = 0;
        for(int i = 0 ; i < nums.size(); i++){
            if(maxV < nums[i]){
                maxV = nums[i];
                v.clear();
                v.push_back(i);
            } else if (maxV == nums[i]){
                v.push_back(i);
            }
        }
        v.push_back(nums.size());
        
        long long ans = 0;
        for(int i = k-1; i < v.size()-1; i++){
            long long r = v[i];
            long long l = v[i - k+1];
            ans += (l+1) * (v[i+1]-r);
        }
        return ans;
    }
};

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

Maximum Number of Tasks You Can Assign  (1) 2025.05.01
Find Numbers with Even Number of Digits  (0) 2025.04.30
Count Subarrays of Length Three With a Condition  (1) 2025.04.27
Count Subarrays With Fixed Bounds  (0) 2025.04.26
Count of Interesting Subarrays  (0) 2025.04.25
블로그 이미지

짬뽕얼큰하게

,

Count Subarrays of Length Three With a Condition

알고리즘 2025. 4. 27. 09:30

Leetcode Problem:

Summary

  • Given an integer array, return the number of subarrays of length 3 such that the sum of the first and third numbers equals exactly half of the second number.

Approach

  • The approach used is to iterate over the array with three nested loops, but with a slight modification
  • Instead of using three nested loops, we use two nested loops and check for the third element
  • We then check if the sum of the first and third elements equals half of the second element, and if so, we increment the count.

Complexity

  • O(n^2)

Explanation

  • The solution iterates over the array with two nested loops, where the outer loop iterates over the first element and the inner loop iterates over the third element
  • For each pair of elements, it checks if the sum of the first and third elements equals half of the second element
  • If so, it increments the count
  • The time complexity is O(n^2) because in the worst case, we need to check all pairs of elements.

Solution Code:


class Solution {
public:
    int countSubarrays(vector& nums) {
        int ans = 0;
        for(int i = 0 ; i < nums.size() - 2; i++){
            if((nums[i] + nums[i+2])*2 == nums[i+1]){
                ans++;
            }
        }
        return ans;
    }
};

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

Find Numbers with Even Number of Digits  (0) 2025.04.30
Count Subarrays Where Max Element Appears at Least K Times  (1) 2025.04.30
Count Subarrays With Fixed Bounds  (0) 2025.04.26
Count of Interesting Subarrays  (0) 2025.04.25
Count Complete Subarrays in an Array  (0) 2025.04.24
블로그 이미지

짬뽕얼큰하게

,

Count Subarrays With Fixed Bounds

알고리즘 2025. 4. 26. 22:01

Leetcode Problem:

Summary

  • Count the number of fixed-bound subarrays in a given array where the minimum and maximum values are within a specified range.

Approach

  • The approach used is to maintain two pointers (jmin and jmax) to track the minimum and maximum values within the current window, and another pointer (jbad) to track the first bad element
  • The result is updated by summing up the number of valid subarrays that can be formed with the current window.

Complexity

  • O(n)

Explanation

  • The time complexity is O(n) because each element in the array is visited once
  • The space complexity is O(1) because only a constant amount of space is used to store the pointers and the result.

Solution Code:


class Solution {
public:
        long long countSubarrays(vector& A, int minK, int maxK) {
        long res = 0, jbad = -1, jmin = -1, jmax = -1, n = A.size();
        for (int i = 0; i < n; ++i) {
            if (A[i] < minK || A[i] > maxK) jbad = i;
            if (A[i] == minK) jmin = i;
            if (A[i] == maxK) jmax = i;
            res += max(0L, min(jmin, jmax) - jbad);
        }
        return res;
    }
};

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

Count Subarrays Where Max Element Appears at Least K Times  (1) 2025.04.30
Count Subarrays of Length Three With a Condition  (1) 2025.04.27
Count of Interesting Subarrays  (0) 2025.04.25
Count Complete Subarrays in an Array  (0) 2025.04.24
Count Largest Group  (0) 2025.04.23
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

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

티스토리툴바